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

procedure citire;
var i,x,y,z:longint;
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 upheap(i:longint);
var k,t:longint;
begin
while I>1 do
        begin
        k:=i shr 1;
        if d^[h[k]]>d^[h[i]] then
                begin
                t:=h[i];h[i]:=h[k];h[k]:=t;
                poz[h[i]]:=i;
                poz[h[k]]:=k;
                i:=i shr 1;
                end
                else break;
        end;
end;

procedure downheap(i,m:longint);
var k,t:longint;
begin
while i shl 1<=m do
        begin
        k:=i shl 1;
        if (k+1<=m)and(d^[h[k+1]]<d^[h[k]]) then inc(K);
        if d^[h[k]]<d^[h[i]] then
                  begin
                  t:=h[i];h[i]:=h[k];h[k]:=t;
                  poz[h[i]]:=i;
                  poz[h[k]]:=k;
                  i:=k;
                  end
                  else break;
        end;
end;

procedure dijkstra;
var i,x:longint;p:lista;
begin
new(D);
new(T);
d^[1]:=0;
t^[1]:=0;
poz[1]:=1;
h[1]:=1;
for i:=2 to n do
        begin
        t^[i]:=maxlongint;
        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);
        downheap(1,k);
        p:=a[min];
        while p<>nil do
                begin
                if t^[p^.nod]=maxlongint then
                        begin
                        inc(K);
                        h[k]:=p^.nod;
                        poz[h[k]]:=k;
                        t^[h[k]]:=min;
                        d^[h[k]]:=d^[min]+P^.cost;
                        upheap(K);
                        end
                        else
                        if d^[p^.nod]>d^[min]+P^.cost then
                                        begin
                                        d^[p^.nod]:=d^[min]+P^.cost;
                                        t^[p^.nod]:=min;
                                        upheap(poz[p^.nod]);
                                        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 t^[i]<>maxlongint then write(d^[i],' ')
        else write(0,' ');
close(output);
end;

begin
citire;
dijkstra;
afisare;
end.