program dijkstra;

var
f:text;
a:array[1..31000,1..31000] of integer;
i,j,n,m,k,x:longint;

begin
 assign(f,'dijkstra.in');
 reset(f);
 for i:=1 to n do for j:=1 to n do a[i,j]:=0;
 readln(f,n,m);
 for i:=1 to m do
        begin
        read(f,j,k,x);
        a[j,k]:=x;
       end;
 for k:=2 to n do for j:=2 to n do
        if (k<>j) and (a[1,k]<>0) and (a[k,j]<>0) and ((a[1,k]+a[k,j]<a[1,j]) or (a[1,j]=0)) then a[1,j]:=a[1,k]+a[k,j];
 for i:=2 to n do write(a[1,i],' ');
 close(f);
 readln;
end.