{
TASK: oldmap
LANG: PASCAL
}
Type pp = record
            dest, st : longint;
end;

const maxn=501;
var a : array[1..maxn, 1..maxn] of longint;
    min, x ,y, BrHeap, i, j, m, k, l, n : longint;
    taken, dist, from : array[1..maxn]of longint;

Procedure readin;
begin
  readln( n);
  for i:=1 to n do begin
    for j:=1 to n do read( a[i, j]);
  end;
end;

Procedure de(v : longint);
begin
  taken[v]:=1;
  for i:=1 to n do begin
    y:=dist[v]+a[v, i];
    if ( taken[i]=0 )and( y<=dist[i] ) then begin
      if dist[i]=y then inc(from[i]);
      dist[i]:=y;
    end;
  end;
  min:=99999999;
  for i:=1 to n do
    if ( min>dist[i] )and( taken[i]=0 ) then begin
      min:=dist[i];
      x:=i;
    end;
  if min<99999999 then de(x);
end;

Begin
  readin;
  for k:=1 to n do begin
    for i:=1 to n do taken[i]:=0;
    for i:=1 to n do dist[i]:=99999999;
    dist[k]:=0;
    for i:=1 to n do from[i]:=0;
    de(k);
    for i:=1 to n do
      if (a[k ,i]=dist[i]) and (i>k)and( from[i]=0 ) then writeln(k, ' ', i, ' ', dist[i]);
  end;


End.