type lista=^nod;
nod=record
nod:word;
cost:word;
next:lista;
end;
vec=array[1..50000] of longint;
var a:array[1..50000] of lista;
n,i,j,k,l,min,m:longint;
d:vec;
h,poz:array[1..50001] of word;

procedure citire;
var i,z:longint;x,y:word;
c:lista;
begin
assign(input,'dijkstra.in');
reset(input);
readln(n,m);
for i:=1 to m do
        begin
        readln(x,y,z);
        new(C);c^.nod:=y;c^.cost:=z;c^.next:=a[x];a[x]:=c;
        end;
close(input);
end;



procedure dijkstra;
var i,x,t:longint;p:lista;
begin
d[1]:=0;
poz[1]:=1;
h[1]:=1;
for i:=2 to n do
        begin
        d[i]:=maxlongint;
        end;
k:=1;
while k>0 do
        begin
        min:=h[1];
        x:=h[1];h[1]:=h[k];h[k]:=x;
        poz[h[1]]:=1;
        poz[h[k]]:=k;
        dec(K);
        i:=1;
        while i shl 1<=k do
        begin
        m:=i shl 1;
        if (m+1<=k)and(d[h[m+1]]<d[h[m]]) then inc(m);
        if d[h[m]]<d[h[i]] then
                  begin
                  t:=h[i];h[i]:=h[m];h[m]:=t;
                  poz[h[i]]:=i;
                  poz[h[m]]:=m;
                  i:=m;
                  end
                  else break;
        end;

        p:=a[min];
        while p<>nil do
                begin
                if poz[p^.nod]=0 then
                        begin
                        inc(K);
                        h[k]:=p^.nod;
                        poz[h[k]]:=k;
                        d[h[k]]:=d[min]+P^.cost;
                        i:=k;
                        while I>1 do
        begin
        m:=i shr 1;
        if d[h[m]]>d[h[i]] then
                begin
                t:=h[i];h[i]:=h[m];h[m]:=t;
                poz[h[i]]:=i;
                poz[h[m]]:=m;
                i:=i shr 1;
                end
                else break;
        end;

                        end
                        else
                        if d[p^.nod]>d[min]+P^.cost then
                                        begin
                                        d[p^.nod]:=d[min]+P^.cost;
                                        i:=poz[P^.nod];
                                        while I>1 do
        begin
        m:=i shr 1;
        if d[h[m]]>d[h[i]] then
                begin
                t:=h[i];h[i]:=h[m];h[m]:=t;
                poz[h[i]]:=i;
                poz[h[m]]:=m;
                i:=i shr 1;
                end
                else break;
        end;

                                        end;
                p:=p^.next;
                end;
        end;


end;

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

begin
citire;
dijkstra;
afisare;
end.