type lista=^element;
     element=record
        cost,edge:word;
        next:lista;
        end;

const nmax=50001;
      inf=maxint;

var i,j,m,n,min,t:longint;
    list:array[1..nmax] of lista;
    h,poz,d:array[1..nmax] of word;
    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;

        new(p);
        p^.cost:=c;
        p^.edge:=a;
        p^.next:=list[b];
        list[b]:=p;
        end;
close(input);
end;
procedure down(i,n:longint);
var v,tata,fiu: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[h[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
tata:=i shr 1; fiu:=i;
while (tata<>0) and (d[h[tata]]>d[h[fiu]]) do
        begin
        poz[h[tata]]:=fiu;
        poz[h[fiu]]:=tata;

        aux:=h[tata];
        h[tata]:=h[fiu];
        h[fiu]:=aux;

        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;
while t>2 do
        begin
        min:=h[1];
        h[1]:=h[t];
        t:=t-1;
        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],t);
                        end;
                p:=p^.next;
                end;
        end;
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;

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