program dijkstra;
const maxn=50001;
      maxm=250001;
      maxc=1001;
      INF=2147483640;
type inod=1..maxn;
     arc=0..maxm;
     cost=0..maxc;
     pnod=^nod;
     nod=record
     inf:inod;
     c:cost;
     next:pnod;
     end;
var f,g:text; n:inod; m:arc; A:array[inod] of pnod; i:longint;
D:array[inod] of longint;
procedure citire;
var x,y:inod; z:cost; q:pnod;
begin
Readln(f,n,m);
For i:=1 to m do
 begin
 Readln(f,x,y,z);
 new(q);
 q^.inf:=y;
 q^.c:=z;
 q^.next:=A[x];
 A[x]:=q;
 end;
end;
procedure drumuri_minime;
var Cd:array[inod] of inod; viz,inCd:array[inod] of byte; x:pnod;
    ps,pi:inod;
begin
pi:=1; ps:=1; Cd[1]:=1;
For i:=1 to n do D[i]:=INF;
For i:=1 to n do viz[i]:=0;
For i:=1 to n do inCd[i]:=0;
viz[1]:=1; inCd[1]:=1; D[1]:=0;
While ps<=pi do
 begin
 x:=A[Cd[ps]];
 While x<>nil do
  begin
  If viz[x^.inf]=0 then
   begin
   If inCd[x^.inf]=0 then
    begin
    inc(pi);
    Cd[pi]:=x^.inf;
    inCd[x^.inf]:=1;
    end;
   If D[Cd[ps]]+x^.c<D[x^.inf] then D[x^.inf]:=D[Cd[ps]]+x^.c;
   end;
  x:=x^.next;
  end;
 viz[Cd[ps]]:=1;
 inc(ps);
 end;
end;
begin
Assign(f,'dijkstra.in'); Reset(f);
Assign(g,'dijkstra.out');Rewrite(g);
citire;  Close(f);
drumuri_minime;
For i:=2 to n do
 If D[i]=INF then Write(g,'0 ')
             else Write(g,D[i],' ');
Close(g);
end.