var n,m,i,j,k,c:integer;
    a:array[1..100,1..100] of word;


begin
assign(input,'royfloyd.in');reset(input);
 readln(n,m);
 for k:=1 to m do
     begin
     readln(i,j,c);
     a[i,j]:=c;
     end;
 close(input);

 for k:=1 to n do
     for i:=1 to n do
         if (i<>k) and (a[i,k]<>0)then
            for j:=1 to n do
                if (j<>k) and (a[k,j]) and (a[i,j]>a[i,k]+a[k,j]) then
                   a[i,j]:=a[i,k]+a[k,j];

assign(output,'royfloyd.out'); rewrite(output);
for i:=1 to n do
    begin
    for j:=1 to n do
        	write(a[i,j],' ')
    writeln;
    end;
close(output);
end.