{
TASK: oldmap
LANG: PASCAL
}

{$R-}
Const
maxN = 500;
maxL = 10000;
Type
 el = record
        vr : word;
        St : longint;
      end;
var
a : array[1..maxN, 0..maxN] of longint;
b : array[1..maxN, 0..maxN] of el;
Used : array[1..maxN] of boolean;
i, j, k, l, m, n, path, search, found : longint;

Procedure DFS (vr : longint);
var
 i, j,  en : longint;
 Op : array[1..maxl] of el;
begin
Op[1].vr:=vr;
op[1].St:=0;
Used[vr]:=true;
en:=1;
i:=1;
While (i<>en+1) and (Used[search]=False) do
  begin
    for j:=1 to b[op[i].vr, 0].vr do
      if not Used[b[op[i].vr, j].vr] then
        begin
          inc(en);
          if en>maxL then
            en:=1;
          op[en].vr:=b[op[i].vr, j].vr;
          op[en].St:=op[i].st+b[op[i].vr, j].st;
          Used[b[op[i].vr, j].vr]:=true;
          if Used[Search] then
            begin
              Found:=op[en].St;
              break;
            end;
        end;
    inc(i);
    if i>maxL then
      i:=1;
  end;
End;


begin
readln(n);
for i:=1 to n do
  begin
    for j:=1 to n do
      read(a[i, j]);
    readln;
  end;
i:=1;
for j:=1 to n do
  if j<>i then
    begin
      inc(b[i, 0].vr);
      b[i, b[i, 0].vr].vr:=j;
      b[i, b[i, 0].vr].St:=a[i, j];
      inc(b[j, 0].vr);
      b[j, b[j, 0].vr].vr:=i;
      b[j, b[j, 0].vr].St:=a[i, j];
    end;

for i:=2 to n-1 do
  for j:=i+1 to n do
    begin
      Search:=j;
      path:=0;
      fillchar(Used, SizeOf(Used), false);
      DFS(i);
      if Found>a[i, j] then
        begin
          inc(b[i, 0].vr);
          b[i, b[i, 0].vr].vr:=j;
          b[i, b[i, 0].vr].St:=a[i, j];
          inc(b[j, 0].vr);
          b[j, b[j, 0].vr].vr:=i;
          b[j, b[j, 0].vr].St:=a[i, j];
        end;
    end;
Fillchar(Used, SizeOf(used), false);

for i:=1 to n do
begin
  Used[i]:=true;
  for j:=1 to b[i, 0].vr do
    if not Used[b[i, j].vr] then
      writeln(i, ' ', b[i, j].vr, ' ', b[i, j].st);
end;

END.
