type lista=^element;
     element=record
                nod,cost:longint;
                a:lista;
             end;
var min,n,m,j,i,q,w,e,nr:longint;
    d:array[1..50001] of longint;
    viz:array[1..50001] of 0..1;
    c:array[1..50001] of lista;
    p:lista;
begin
assign(input,'dijkstra.in'); reset(input);
assign(output,'dijkstra.out'); rewrite(output);
readln(n,m);
for i:=2 to n do begin viz[i]:=0; d[i]:=1000000001; end;
for i:=1 to m do
  begin
    readln(q,w,e);
    new(p);
    p^.nod:=w;
    p^.cost:=e;
    p^.a:=c[q];
    c[q]:=p;
  end;
p:=c[1];
while p<>nil do
   begin
     d[p^.nod]:=p^.cost;
     p:=p^.a;
   end;
nr:=1; viz[1]:=1;
while nr<n do
   begin
     min:=1000000001;
     for i:=2 to n do if (d[i]<min)and(viz[i]=0) then begin min:=d[i]; q:=i;end;
     inc(nr);
     viz[q]:=1;
     p:=c[q];
     while p<>nil do
         begin
           if (p^.cost+d[q]<d[p^.nod])and(viz[p^.nod]=0) then d[p^.nod]:=d[q]+p^.cost;
           p:=p^.a;
         end;
   end;
for i:=2 to n do if d[i]=1000000001 then write(0,' ') else write(d[i],' ');
close(input);
close(output);
end.