//dijkstra v3.0 :P
type lista=^element;
     element=record
        edge,cost:word;
        next:lista;
        end;
const inf=maxint;
      nmax=500001;
var list:array[1..nmax] of lista;
    poz,h,d:array[1..nmax] of longint;
    n,m,i,j,min,t:longint;
    p:lista;

procedure citire;
var a,b,c:longint;
begin
assign(input,'dijkstra.in');reset(input);
read(n,m);
for i:=1 to m do
        begin
        read(a,b,c);
        new(p);
        p^.cost:=c;
        p^.edge:=b;
        p^.next:=list[a];
        list[a]:=p;
        end;
close(input);
end;

procedure afisare;
begin
assign(output,'dijkstra.out');rewrite(output);
for i:=2 to n do
        if d[i]=inf then write(0,' ')
                    else write(d[i],' ');
close(output);
end;

procedure down(i,n:longint);
var tata,fiu,v:longint;
begin
v:=h[i];tata:=i;fiu:=i shl 1;
while fiu<=n do
        begin
        if fiu<n then
                if(d[h[fiu]]>d[h[fiu+1]]) then fiu:=fiu+1;
        if d[v]>d[h[fiu]] then
                begin
                h[tata]:=h[fiu];
                poz[h[fiu]]:=tata;
                tata:=fiu;
                fiu:=fiu shl 1;
                end
                else
                fiu:=n+1;
        end;
h[tata]:=v;
poz[h[tata]]:=tata;
end;

procedure up(i,n:longint);
var tata,fiu,aux:longint;
begin
fiu:=i; tata:=i shr 1;
while (tata<>0) and (d[h[tata]]>d[h[fiu]]) do
                begin
                aux:=h[fiu];
                h[fiu]:=h[tata];
                h[tata]:=aux;
                poz[h[fiu]]:=tata;
                poz[h[tata]]:=fiu;

                fiu:=tata;
                tata:=tata shr 1;
                end;
end;

procedure creare_h;
begin
for i:=1 to n do
        begin
        h[i]:=i;
        poz[i]:=i;
        d[i]:=inf;
        end;
d[1]:=inf+1;
p:=list[1];
while p<>nil do
        begin
        d[p^.edge]:=p^.cost;
        p:=p^.next;
        end;
end;

procedure dijkstra;
begin
creare_h;

for i:=(n shr 1) downto 1 do
        down(i,n);
t:=n;

for i:=2 to n do
        begin
        min:=h[1];
        h[1]:=h[t];
        h[t]:=inf;
        dec(t);
        down(1,t);
        p:=list[min];
        while p<>nil do
                begin
                if d[p^.edge]>d[min]+p^.cost then
                        begin
                        d[p^.edge]:=d[min]+p^.cost;
                        up(poz[p^.edge],n);
                        end;
                p:=p^.next;
                end;
        end;
end;

begin {main}
citire;
dijkstra;
afisare;
end.