{
TASK: oldmap
LANG: PASCAL
}
{$R-}
const
 maxn=501;
type
  reb = record p , q , t : longint; end;
var
  a : array[0..maxn,0..maxn] of longint;
  b : array[0..maxn,0..maxn] of boolean;
  h : array[0..maxn*maxn] of reb;
  n,br : longint;
  used : array[0..maxn] of boolean;
  p    : array[0..maxn] of longint;
  ansbr,i,j,size: longint;
  ver : array[0..(maxn*maxn) div 2] of reb;
procedure vhod;
begin
   readln(n);
   for i:=1 to n do
   begin
      for j:=1 to n do
      begin
         read(a[i,j]);
      end;
      readln;
   end;
end;
procedure swap(var a ,b : reb);
var
 tmp : reb;
begin
   tmp:=a;
   a:=b;
   b:=tmp;
end;
procedure getmin(var x : reb);
var
 cr , pr1 , pr2 : longint;
begin
   x:=h[1];
   h[1]:=h[size];
   dec(size);
   cr:=1;
   repeat
      pr1:=cr shl 1;
      pr2:=pr1+1;
      if pr2<=size then
      begin
         if (h[pr1].t<h[cr].t)or(h[pr2].t<h[cr].t) then
         begin
            if h[pr1].t<h[pr2].t then
            begin
               swap(h[cr],h[pr1]);
               cr:=pr1;
            end
            else
            begin
               swap(h[cr],h[pr2]);
               cr:=pr2;
            end;
         end;
      end
      else
      if (pr1=size)and(h[pr1].t<h[cr].t) then
      begin
         swap(h[cr],h[pr1]);
         cr:=pr1;
         break;
      end
      else
      break;
   until false;
end;
procedure AddNew(x : reb);
var
 pr, cr : longint;
begin
   inc(size);
   h[size]:=x;
   cr:=size;
   pr:=cr shr 1;
   if pr>0 then
   while h[cr].t<h[pr].t do
   begin
      swap(h[cr],h[pr]);
      cr:=pr;
      pr:=cr shr 1;
      if pr<1 then break;
   end;
end;
procedure main;
var
 x : reb;
 i : longint;
 minr : reb;
begin
   for i:=1 to n do b[i,i]:=true;
   used[1]:=true;
   inc(p[0]);
   p[p[0]]:=1;
   for i:=2 to n do
   begin
      x.p:=1;
      x.q:=i;
      x.t:=a[1,i];
      AddNew(x);
   end;
   br:=sqr(n)-n;
   while br>0  do
   begin
      GetMin(minr);
      if not b[minr.p,minr.q] then
      begin
         inc(ansbr);
         ver[ansbr]:=minr;
         b[minr.p,minr.q]:=true;
         b[minr.q,minr.p]:=true;
      end;
      for j:=1 to p[0] do
         if b[p[j],minr.p] then
          if a[p[j],minr.q]=a[p[j],minr.p]+minr.t then
         begin
            b[p[j],minr.q]:=true;
            b[minr.q,p[j]]:=true;
            dec(br);
         end;
      for j:=1 to p[0] do
         if b[p[j],minr.q] then
          if a[p[j],minr.p]=a[p[j],minr.q]+minr.t then
         begin
            b[p[j],minr.p]:=true;
            b[minr.p,p[j]]:=true;
            dec(br);
         end;
         if not used[minr.q] then
         begin
            inc(p[0]);
            p[p[0]]:=minr.q;
            used[minr.q]:=true;
            for j:=1 to n do
            if not used[j] then
            begin
               x.p:=minr.q;
               x.q:=j;
               x.t:=a[minr.q,j];
               AddNew(x);
            end;
         end;
   end;
end;
procedure izhod;
begin
   for i:=1 to ansbr do
   begin
      writeln(ver[i].p,' ',ver[i].q,' ',ver[i].t);
   end;
end;
begin
   vhod;
   main;
   izhod;
end.
