type adresa=^nod;
     nod= record inf,cst:longint; adr:adresa; end;


var n,m,i,k:longword;
    p:array[1..50000] of adresa;

    d:array[1..50000] of longint;
    poz,h:array[1..50000] of longint;

procedure citire;
        var f:text;
            i,x,y,c:longword;
            q:adresa;
        begin
        assign(f,'dijkstra.in');
        reset(f);
        readln(f,n,m);
        for i:=1 to n do p[i]:=nil;
        for i:=1 to m do begin
            readln(f,x,y,c);
            new(q);
             q^.inf:=y; q^.cst:=c;
             q^.adr:=p[x];
             p[x]:=q;

            end;
        close(f);
        end;

procedure scrie;
        var f:text;
            i:longword;
        begin
        assign(f,'dijkstra.out');
         rewrite(f);
         for i:=2 to n do
             write(f,d[i],' ');
         close(f);
        end;

procedure swap(x,y:longword);
        var t:longword;
        begin
        t:=h[x]; h[x]:=h[y]; h[y]:=t;
        t:=poz[x]; poz[x]:=poz[y]; poz[y]:=t;
        end;

procedure corect_heap_sus(p,c:longword);
        begin
        while (p>=1) do
         if d[h[p]]>d[h[c]] then begin
            swap(p,c);
            c:=p;
            p:=p shr 1;
         end else p:=0;
        end;

procedure corect_heap_jos(p,k:longword);
        var c: longword;
        begin
        c:=p shl 1;
         while (c<=k) do begin
         if (c+1<=k) and (d[h[c]]>d[h[c+1]]) then
                inc(c);
         if (d[h[p]]>d[h[c]]) then begin
            swap(p,c);
            p:=c;
            c:=c shl 1;
         end;
         end;
        end;



procedure dijkstra_heap;
   var i,min,k,t,pz:longword;
       q:adresa;
   begin
   for i:=2 to n do
       begin
       d[i]:=1 shl 30;
       poz[i]:=-1;
       end;
   d[1]:=0;
   h[1]:=1;
   poz[1]:=1;
   k:=1;
   while k<>0 do begin
         min := h[1];

         t:=h[1]; h[1]:=h[k]; h[k]:=t;
         dec(k);
         poz[h[1]]:=1;

         corect_heap_jos(1,k);


         q:=p[min];
         while q<>nil do begin
           if (d[q^.inf]>d[min]+q^.cst) then begin
              d[q^.inf]:=d[min]+q^.cst;
              if poz[q^.inf]=-1 then begin
                 inc(k); h[k]:=q^.inf; pz:=k; poz[q^.inf]:=k;
              end else pz:=poz[q^.inf];
              corect_heap_sus(pz shr 1,pz);
           end;
           q:=q^.adr;
         end;
        end;
   end;


begin
citire;
dijkstra_heap;
scrie;
end.