program dikstr;
var A : array [1..10000,1..10000] of -1..1000;
    S,D : array [1..10000] of longint;
    m,n,i,j,l,min,poz : integer;
    f,g : text;
begin
assign(f,'dijkstra.in');
reset(f);
assign(g,'dijkstra.out');
rewrite(g);

readln(f,n,m);

for i := 1 to n do begin
S[i] := 0 ;
for j := 1 to n do
A[i,j] := -1;
end;


for l := 1 to m do begin
read(f,i,j);
readln(f,A[i,j]);
end;


S[1] := 1;
for i := 1 to n do
if A[1,i]=-1 then D[i] := 2000000
             else D[i] := A[1,i];


for i := 1 to n-1 do begin
min := 30000;
for j := 1 to n do
if S[j]=0 then
          if D[j]<min then begin
                           min := D[j];
                           poz := j;
                           end;
S[poz] := 1;

for j := 1 to n do
if S[j]=0 then
        if A[poz,j]<>-1 then
                        if D[j]>D[poz]+A[poz,j] then D[j] := D[poz]+A[poz,j];

end;

for i := 2 to n do
if D[i]<2000000 then write(g,D[i],' ')
                else write(g,'0 ');

close(f);
close(g);
end.