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 n do a[i]:=nil;
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);
var k,t:word;
begin
k:=i shr 1;
while (k>=1) and (d[h[k]]>d[h[i]]) do
        begin
        h[i]:=h[i] xor h[k];h[k]:=h[k] xor h[i];h[i]:=h[k] xor h[i];
        poz[h[i]]:=i;
        poz[h[k]]:=k;
        i:=k;
        k:=k shr 1;
        end;
end;

procedure downheap(i,m:word);
var k,t:word;
begin
k:=i shl 1;
while k<=m do
        begin
        if (k+1<=m)and(d[h[k+1]]<d[h[k]]) then inc(K);
        if d[h[k]]<d[h[i]] then
                  begin
				h[i]:=h[i] xor h[k];h[k]:=h[k] xor h[i];h[i]:=h[k] xor h[i];
                  poz[h[i]]:=i;
                  poz[h[k]]:=k;
                  i:=k;
                  k:=k shl 1;
                  end
                  else break;
        end;
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];
        h[1]:=h[1] xor h[k];h[k]:=h[k] xor h[1];h[1]:=h[k] xor h[1];
        poz[h[1]]:=1;
        poz[h[k]]:=k;
        dec(K);
        downheap(1,k);
        p:=a[min];
        while p<>nil do
                begin
                if d[p^.nod]>d[min]+P^.cost then
                begin
                d[p^.nod]:=d[min]+P^.cost;
                if poz[p^.nod]=0 then
                        begin
                        inc(K);
                        h[k]:=p^.nod;
                        poz[h[k]]:=k;
                        t:=k;
                        end
                        else
                            t:=poz[p^.nod];
                upheap(T);
                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.