type pnod=^nod;
     nod=record
     inf,cost:longint;
     urm:pnod;
     end;
var v:array [1..50000] of pnod;
    h,d,poz,viz:array [1..50000] of longint;
    n,i,j,k,m,x,c,y:longint;
    q:pnod;
    f,g:text;

procedure inv(var x,y:longint);
var aux:longint;
          begin
          aux:=x;
          x:=y;
          y:=aux;
          end;

procedure addlist(x,y,c:longint);
var q:pnod;
          begin
          if v[x]=nil then
             begin
             new(q);
             q^.inf:=y;
             q^.cost:=c;
             q^.urm:=nil;
             v[x]:=q;
             end
             else
             begin
             new(q);
             q^.inf:=y;
             q^.cost:=c;
             q^.urm:=v[x];
             v[x]:=q;
             end;
          end;

procedure siftup(i:longint);
          begin
          if i<>1 then
             if d[h[i]]<d[h[i div 2]] then
                begin
                inv(h[i],h[i div 2]);
                inv(poz[h[i]],poz[h[i div 2]]);
                siftup(i div 2);
                end;
          end;

procedure addheap(i:longint);
          begin
          h[i]:=i;
          siftup(i);
          end;

procedure siftdown(i,k:longint);
var fiu:longint;
          begin
          fiu:=i;
          if i*2<=k then
             if d[h[i]]>d[h[i*2]] then
                fiu:=2*i;
          if i*2+1<=k then
             if d[h[fiu]]>d[h[i*2+1]] then
                fiu:=2*i+1;
          if fiu<>i then
             begin
             inv(h[i],h[fiu]);
             inv(poz[h[i]],poz[h[fiu]]);
             siftdown(fiu,k);
             end;
          end;

begin
assign(f,'dijkstra.in');reset(f);
readln(f,n,m);
for i:=1 to n do
    begin
    d[i]:=2000000000;
    poz[i]:=i;
    v[i]:=nil;
    end;
for i:=1 to m do
    begin
    readln(f,x,y,c);
    addlist(x,y,c);
    if x=1 then
       d[y]:=c;
    end;
close(f);
d[1]:=0;viz[1]:=1;
for i:=2 to n do
    addheap(i-1);
k:=n-1;

//Dijkstra
for i:=1 to n-1 do
    begin
    j:=h[1];
    viz[j]:=1;
    inv(h[1],h[k]);
    inv(poz[h[1]],poz[h[k]]);
    k:=k-1;
    siftdown(1,k);
    q:=v[j];
    while q<>nil do
          begin
          if (d[q^.inf]>d[j]+q^.cost) and (viz[q^.inf]=0) then
              begin
              d[q^.inf]:=d[j]+q^.cost;
              siftdown(poz[q^.inf],k);
              end;
          q:=q^.urm;
          end;
    end;
assign(g,'dijkstra.out');rewrite(g);
for i:=2 to n do
    if d[i]=2000000000 then
       write(g,'0 ')
       else
       write(g,d[i],' ');
close(g);
end.