var a:array[1..100,1..100]of longint;
i,j,k,n,m,x,y:longint;
begin
   readln(n,m);
   filldword(a,sizeof(a) div 4,maxlongint shr 1);
   for i:=1 to n do
     begin
       readln(x,y,a[x,y]);
       a[y,x]:=a[x,y];
     end;
   for i:=1 to m do
     a[i,i]:=0;
   for i:=1 to m do
     for j:=1 to m do
       if i<>j then
         for k:=1 to m do
           if (i<>k) and (j<>k) then
             if a[j,i]+a[i,k]<a[j,k] then
               a[j,k]:=a[j,i]+a[i,k];
   for i:=1 to m do
     begin
       for j:=1 to m do
         write(a[i,j],' ');
       writeln;
     end;
end.