const infile='dijkstra.in';
  outfile='dijkstra.out';
  maxn=50003;
  inf=50000003;
type list=^nod;
  nod=record
        inf,cost:longint;
        next:list;
        end;
var a:array[0..maxn]of list;
  d:array[0..maxn]of 0..inf;
  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); new(p); p^.inf:=j; p^.cost:=k;
     p^.next:=a[i]; a[i]:=p; dec(m);
     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;

 function ExMinim:longint;
 begin
   ExMinim:=h[1]; h[1]:=h[vf]; dec(vf); combinare(1);
 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 init;
 var i:longint;
   p:list;
 begin
   st:=1;
   for i:=1 to n do begin d[i]:=inf; up[i]:=-1; end;
   d[st]:=0; up[st]:=1;
   p:=a[st];
   while(p<>nil)do begin
     inc(vf); h[vf]:=p^.inf; d[p^.inf]:=p^.cost; up[p^.inf]:=vf;
     p:=p^.next;
     end;
   for i:=vf shr 1 to 1 do combinare(i);
 end;

 procedure relaxeaza(u,v,w:longint);
 begin
   if(d[v]>d[u]+w)then begin
     d[v]:=d[u]+w;
     if(up[v]<>-1)then insert(up[v])
     else begin inc(vf); h[vf]:=v; up[v]:=vf; insert(vf); end;
     end;
 end;

 procedure dijkstra;
 var min:longint;
   p:list;
 begin
   init;
   while(vf>0)do begin
     min:=ExMinim; p:=a[min];
     while(p<>nil)do begin relaxeaza(min,p^.inf,p^.cost); 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]<>inf)then write(d[i],' ')
    else write(0,' ');
   close(output);
 end;

begin
citire; dijkstra; scrie;
end.