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 upheap(i:word); inline;
var k,t:word;
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:word);inline;
var k,t:word;
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
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);
        downheap(1,k);
        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;
                        upheap(K);
                        end
                        else
                        if d[p^.nod]>d[min]+P^.cost then
                                        begin
                                        d[p^.nod]:=d[min]+P^.cost;
                                        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 poz[i]<>0 then write(d[i],' ')
        else write(0,' ');
close(output);
end;

begin
citire;
dijkstra;
afisare;
end.