program sss;
var f,g:text;
    n,i,j,k:longint;
    a,b:array[1..300,1..300] of longint;
begin
assign(f,'rf.in'); reset(f);
assign(g,'rf.out'); rewrite(g);
readln(f,n);
  for i:=1 to n do
    for j:=1 to n do
    begin
       read(f,a[i,j]);
       b[i,j]:=1;
       b[i,i]:=0;
    end;
  for k:=1 to n do
  begin
     for i:=1 to n do
       for j:=1 to n do

          if a[i,j]>a[i,k]+a[k,j] then
          begin
             a[i,j]:=a[i,k]+a[k,j];
             if i<>j then
               if b[i,j]<b[i,k]+b[k,j] then
                 b[i,j]:=b[i,k]+b[k,j];
          end
          else
          if a[i,j]=a[i,k]+a[k,j] then
             begin
               if i<>j then
                 if b[i,j]<b[i,k]+b[k,j] then
                   b[i,j]:=b[i,k]+b[k,j];
             end;
      end;
      for i:=1 to n do
      begin
        for j:=1 to n do
          begin
            write(g,a[i,j],' ');
          end;
          writeln(g);
      end;
      writeln(g);
     for i:=1 to n do
     begin
       for j:=1 to n do
         begin
           write(g,b[i,j],' ');
         end;
       writeln(g);
     end;
close(f);
close(g);
end.