uses crt,dos;
var a:array[1..100,1..100]of integer;
    i,j,n:integer;
    f:text;
    h,m,s,s100:word;
procedure rf;
var k,j,i:integer;
    g:text;
 begin
 assign(g,'royfloyd.out');
 rewrite(g);
 for k:=1 to n do
   for j:=1 to n do
     for i:=1 to n do
        if a[i,j]>a[i,k]+a[k,j] then a[i,j]:=a[i,k]+a[k,j];
 for i:=1 to n do
   begin
   for j:=1 to n do
      if i=j then write(g,0,' ')
           else write(g,a[i,j],' ');
   writeln(g);
   end;
 close(g);
 end;
begin
clrscr;
gettime(h,m,s,s100);
writeln(h,':',m,':',s,':',s100);
assign(f,'royfloyd.in');
reset(f);
read(f,n);
for i:=1 to n do
   for j:=1 to n do
   begin
   read(f,a[i,j]);
   if a[i,j]=0 then a[i,j]:=1001;
   end;
close(f);
rf;
gettime(h,m,s,s100);
writeln(h,':',m,':',s,':',s100);
end.