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[1..2000000] of inod; x:pnod;
    ps,pi:longint;
begin
pi:=1; ps:=1; Cd[1]:=1;
For i:=1 to 50000 do D[i]:=INF;
D[1]:=0;
While ps<=pi do
 begin
 If pi>1000000 then
  begin
  For i:=1 to pi-ps do
   Cd[i]:=Cd[i+ps-1];
  pi:=pi-ps;
  ps:=1;
  end;
 x:=A[Cd[ps]];
 While x<>nil do
  begin
  If D[Cd[ps]]+x^.c<D[x^.inf] then
     begin
     D[x^.inf]:=D[Cd[ps]]+x^.c;
     inc(pi);
     Cd[pi]:=x^.inf;
     end;
  x:=x^.next;
  end;
 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.