const infile='dijkstra.in';
  outfile='dijkstra.out';
  maxn=50003;
  infinit=50000003;
type list=^nod;
  nod=record
        inf,cost:longint;
        next:list;
        end;
var a:array[0..maxn]of list;
  d:array[0..maxn]of longint;
  h,up:array[0..maxn]of longint;
  n,m,st,vf:longint;

 procedure citire;
 var i,j,k:longint;
   p:list;
 begin
   assign(input,infile); reset(input); readln(n,m);
   while(m>0)do begin
     readln(i,j,k); dec(m);
     new(p); p^.inf:=j; p^.cost:=k; p^.next:=a[i]; a[i]:=p;
     end;
   close(input);
 end;

 procedure combinare(i:longint);
 var v,tata,fiu:longint;
 begin
   tata:=i; fiu:=tata shl 1; v:=h[tata];
   while(fiu<=vf)do begin
     if(fiu<vf)and(d[h[fiu]]>d[h[fiu+1]])then inc(fiu);
     if(d[v]>d[h[fiu]])then begin
       up[h[fiu]]:=tata; h[tata]:=h[fiu];
       tata:=fiu; fiu:=fiu shl 1;
       end
     else fiu:=vf+1;
     end;
   up[v]:=tata; h[tata]:=v;
 end;

 procedure insert(vf:longint);
 var v,tata,fiu:longint;
 begin
   v:=h[vf]; fiu:=vf; tata:=vf shr 1;
   while(tata<>0)and(d[h[tata]]>d[v])do begin
     up[h[tata]]:=fiu; h[fiu]:=h[tata];
     fiu:=tata; tata:=fiu shr 1;
     end;
   up[v]:=fiu; h[fiu]:=v;
 end;

 procedure dijkstra;
 var min,u:longint;
   p:list;
 begin
   for u:=2 to n do begin d[u]:=infinit; up[u]:=-1; end;
   d[1]:=0; up[1]:=1; h[1]:=1; vf:=n;
   while(vf>0)and(h[1]<>infinit)do begin
     min:=h[1]; h[1]:=h[vf]; dec(vf); combinare(1);
     p:=a[min];
     while(p<>nil)do begin
       if(d[p^.inf]>d[min]+p^.cost)then begin
         d[p^.inf]:=d[min]+p^.cost;
         if(up[p^.inf]<>-1)then insert(up[p^.inf])
         else begin inc(vf); h[vf]:=p^.inf; up[p^.inf]:=vf; insert(vf); end;
       end;
       p:=p^.next; end;
     end;
 end;

 procedure scrie;
 var i:longint;
 begin
   assign(output,outfile); rewrite(output);
   for i:=2 to n do
    if(d[i]<>infinit)then write(d[i],' ')
    else write(0,' ');
   close(output);
 end;

begin

citire; dijkstra; scrie;
end.