const nmax=50002;
const mmax=250002;
const inf=2000000000;
type muchie=record
        x,y,cost:longint;
        end;
var v:array of muchie;
d:array[1..nmax]of longint;
i,x,y,c,m,n:longint;
ok:boolean;
f,g:text;
begin
assign(f,'dijkstra.in');
reset(f);
assign(g,'dijkstra.out');
rewrite(g);
read(f,n,m);
setlength(v,n+1);
for i:=1 to m do
   begin
     read(f,x,y,c);
     v[i].x:=x;
     v[i].y:=y;
     v[i].cost:=c;
     if x=1 then d[y]:=c;
   end;
for i:=2 to n do
   if d[i]=0 then d[i]:=inf;
repeat
   ok:=true;
   for i:=1 to m do
      if d[v[i].y]>(d[v[i].x]+v[i].cost) then
             begin
               d[v[i].y]:=d[v[i].x]+v[i].cost;
               ok:=false;
             end;
   until ok;
for i:=2 to n do
if d[i]=inf then write(g,'0 ')
       else write(g,d[i],' ');
close(g);
end.