{
TASK: oldmap
LANG: PASCAL
}

{$R-}
Const
maxN = 500;
Type
 el = record
        vr, 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 : integer;
begin
Used[vr]:=true;
if vr=search then
  begin
    Found:=path;
  end
else
for i:=1 to b[vr,0].vr do
  if not Used[b[vr, i].vr] then
    begin
      inc(path, b[vr, i].St);
      DFS(b[vr, i].vr);
      dec(path, b[vr, i].St);
      if Used[search] then
        break;
    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.