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


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

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

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