program dijkstra;
const maxn=50001;
      maxm=250001;
      maxc=1001;
      INF=2147483640;
type inod=0..maxn;
     arc=0..maxm;
     cost=0..maxc;
     pnod=^nod;
     nod=record
     inf:inod;
     c:cost;
     next:pnod;
     end;
var f,g:text; n,hp:inod; m:arc; A:array[inod] of pnod; i:longint;
D:array[inod] of longint; H,poz:array[inod] of inod;
bufin,bufout:array[1..50000] of byte;
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 swap(var a:inod; var b:inod);
var aux:inod;
begin
aux:=a;
a:=b;
b:=aux;
end;
procedure upheap(k:inod);
begin
While (k>1)and(D[H[k div 2]]>D[H[k]]) do
 begin
 swap(poz[H[k]],poz[H[k div 2]]);
{ poz[H[k div 2]]:=poz[H[k]];
 poz[H[k]]:=k div 2;   }
 swap(H[k],H[k div 2]);
 k:=k div 2;
 end;
end;
procedure downheap(k:inod);
var son:inod;
begin
Repeat
son:=0;
If 2*k<=hp then
 begin
 son:=2*k;
 If (2*k+1<=hp)and(D[H[son]]>D[H[2*k+1]]) then son:=2*k+1;
 If D[H[son]]>=D[H[k]] then son:=0;
 end;
If son>0 then
 begin
 swap(poz[H[son]],poz[H[k]]);
{ poz[H[k]]:=poz[H[son]];
 poz[H[son]]:=son;  }
 swap(H[son],H[k]);
 k:=son;
 end;
Until son=0;
end;

procedure drumuri_minime;   {H[i]= nodul din graf aflat pe pozitia i in heap}
var x:pnod; min:inod;       {poz[i]= pozitia nodului i din graf in heap }
begin
For i:=1 to n do D[i]:=INF;
For i:=1 to n do poz[i]:=0;
D[1]:=0; H[1]:=1;  hp:=1;
While hp>=1 do
 begin
 min:=H[1];
 swap(H[1],H[hp]);     {sterge cel mai mic element din heap (1) }
 poz[H[1]]:=1;
 dec(hp);
 downheap(1);
 x:=A[min];
 While x<>nil do
  begin
  If x^.c+D[min]<D[x^.inf] then
   begin
   D[x^.inf]:=x^.c+D[min];
   If poz[x^.inf]>0 then upheap(poz[x^.inf])
     else
     begin
     inc(hp);
     H[hp]:=x^.inf;
     poz[x^.inf]:=hp;
     upheap(hp);
     end;
    end;
  x:=x^.next;
   end;
 end;
end;
begin
Assign(f,'dijkstra.in'); Reset(f);
settextbuf(f,bufin);
Assign(g,'dijkstra.out');Rewrite(g);
settextbuf(g,bufout);
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.