uses crt;
type mx=array[1..1000,1..1000] of integer;
     vek=array[1..1000] of integer;
var
 w:mx;
 jart,v,os:vek;
 i,kcs,mincs,min,n,m,c,akt,j,a,b:integer;
 f,g:text;
begin
clrscr;
assign(f,'dijkstra.in');
reset(f);
readln(f,n,m);
for i:= 1 to n do
for j:= 1 to n do
if i<>j then w[i,j]:=1000;

for i:=1 to m do
begin
  readln(f,a,b,c);
  w[a,b]:=c;
  w[b,a]:=c;
end;
for i:= 1 to n do
begin
for j:= 1 to n do
 write(w[i,j],' ');
writeln;
end;
writeln;
kcs:=4;
for i:= 1 to n do
begin
 os[i]:=kcs;
 v[i]:=w[kcs,i];
 jart[i]:=0;
end;
jart[kcs]:=1;
mincs:=kcs;
akt:=kcs;
for j:= 1 to n do
begin
min:=10000;
 for i:= 1 to n do
  if (v[i]<min) and (jart[i]=0) then
  begin
  mincs:=i;
  min:=v[i];
  end;
jart[mincs]:=1;
os[mincs]:=akt;
for i:= 1 to n do
 begin
  if min+w[mincs,i]<v[i] then v[i]:=min+w[mincs,i];
 end;
akt:=mincs;
end;
assign(g,'dijkstra.out');
rewrite(g);
for i:= 1 to n do
write (g,v[i],' ');
close(f);
close(g);
end.