{
TASK:oldmap
LANG:PASCAL
}
var a:array[0..501,0..501] of longint;
    heap:array[0..250001,1..2] of longint;
    visit:array[0..500] of boolean;
    d:array[0..500] of longint;
    fl,k3,i,n,k,j,p,i1:longint;
Procedure Read_data;
begin
   readln(N);
   for i:=1 to n do
      begin
         for j:=1 to n do read(a[i,j]);
         readln;
      end;
end;
Procedure Swap(k1,l1:longint);
var t1:longint;
begin
   t1:=heap[k1,1];
   heap[k1,1]:=heap[l1,1];
   heap[l1,1]:=t1;
   t1:=heap[k1,2];
   heap[k1,2]:=heap[l1,2];
   heap[l1,2]:=t1;
end;
Procedure Ins(k1,st1:longint);
var z1:longint;
begin
   inc(p);
   heap[p,1]:=k1;
   heap[p,2]:=st1;
   z1:=p;
   if z1>1 then
   while (z1>1)and(heap[z1,2]<heap[z1 div 2,2]) do
      begin
        swap(z1,z1 div 2);
        z1:=z1 div 2;
     end;
end;
Procedure Delete;
var z1,k2:longint;
begin
   heap[1,1]:=heap[p,1];
   heap[1,2]:=heap[p,2];
   dec(p);
   z1:=p;
   k2:=1;
   fl:=0;
   while (Fl=0)and(k*2<=p) do
      begin
         if ((heap[k2*2,2]<heap[k2*2+1,2])and(k2*2<=p))or((k2*2+1>p)and(k2*2<=p)) then
            begin
               Swap(k2,k2*2);
               k2:=k2*2;
            end
         else if (heap[k2*2,2]>=heap[k2*2+1,2])and(k2*2+1<=p) then
            begin
               Swap(k2,k2*2+1);
               k2:=k2*2+1;
            end
         else FL:=1;
      end;
end;
Procedure Diikstra(f:longint);
Begin
   visit[f]:=true;
   for i:=1 to n do
      if (visit[i]=false) then ins(i,d[f]+a[f,i]);
   k:=0;
   repeat
      k:=heap[1,1];
      k3:=heap[1,2];
      delete;
   until (visit[k]=false)or(p=0);
   if visit[k]=false then begin
   d[k]:=k3;
   Diikstra(k);      end;
End;
Begin
   Read_data;
   for i1:=1 to n do
      begin
         p:=0;
         for j:=1 to n do d[j]:=700000000;
         d[i1]:=0;
         Diikstra(i1);
         for j:=i1+1 to n do
            begin
               fl:=0;
               k:=0;
               repeat
                  inc(k);
                  if (j<>k)and(d[j]>=d[k]+a[k,j])and(k<>i1) then fl:=1;
               until (fl=1)or(k=n);
               if fl=0 then writeln(i1,' ',j,' ',d[j]);
            end;
         for j:=1 to n do
            begin
               visit[j]:=false;
            end;
      end;
End.
