type vec=array[0..50001] of longint;
vec2=array[1..250000] of longint;
var d,t,h,poz,ind:vec;
dir,cost:^vec2;
a,b,c:vec2;
n,i,j,k,l,m,nod:longint;
procedure dijkstra;
var i,x,j,k,y:longint;ok:boolean;
begin
fillchar(d,sizeof(d),63);
fillchar(t,sizeof(t),0);
d[1]:=0;
for i:=1 to n do
        begin
        h[i]:=i;
        poz[i]:=i;
        end;
for i:=1 to n do
        begin
        k:=i;
        while k>1 do
                begin
                x:=k div 2;
                if d[h[k]]<d[h[x]] then
                                   begin
                                   j:=h[k];h[k]:=h[x];h[x]:=j;
                                   poz[h[x]]:=x;poz[h[k]]:=k;   {creare heap}
                                   k:=x;
                                   end
                                   else k:=1;
                end;
        end;
m:=n;
while m>0 do
        begin
        j:=h[m];h[m]:=h[1];h[1]:=j;
        poz[h[1]]:=1;poz[h[m]]:=m;
        dec(M);
        k:=1;
        ok:=true;
        while (k*2<=m) and ok do
                begin
                ok:=false;
                x:=2*k;
                if k*2+1<=m then
                                if d[h[2*k+1]]<d[h[2*k+1]] then
                                                        x:=2*k+1;
                if d[h[x]]<d[h[k]] then
                        begin
                        j:=h[k];h[k]:=h[x];h[x]:=j;
                        poz[h[x]]:=x;poz[h[k]]:=k;
                        k:=x;
                        ok:=true;
                        end;
                end;
        nod:=h[m+1];
        for i:=ind[nod]+1 to ind[nod+1] do
                        if d[dir^[i]]>d[nod]+Cost^[i] then
                                begin
                                d[dir^[i]]:=d[nod]+Cost^[i];
                                t[dir^[i]]:=nod;
                                k:=poz[dir^[i]];
                                while k>1 do
                                begin
                                x:=k div 2;
                                if d[h[k]]<d[h[x]] then
                                   begin
                                   j:=h[k];h[k]:=h[x];h[x]:=j;
                                   poz[h[x]]:=x;poz[h[k]]:=k;   {urca heap}
                                   k:=x;
                                   end
                                   else k:=1;
                                end;
                                end;

        end;





end;


begin
assign(input,'dijkstra.in');
assign(output,'dijkstra.out');
reset(input);
rewrite(output);
readln(n,m);
for i:=1 to m do
        begin
        readln(a[i],b[i],c[i]);
        inc(ind[a[i]]);
        end;
for i:=2 to n do ind[i]:=ind[i]+ind[i-1];
new(dir);
new(cost);
for i:=1 to m do
        begin
        dir^[ind[a[i]]]:=b[i];
        cost^[ind[a[i]]]:=c[i];
        dec(ind[a[i]]);
        end;
dijkstra;

for i:=2 to n do
        if t[i]<>0 then write(d[i],' ')
                else write(0,' ');

close(input);
close(output);
end.