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,h,d,poz:^vec;

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);
new(poz);
new(H);
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.