const infi:longint=1061109567;
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),63);
d[1]:=0;
h[1]:=1;
poz[1]:=1;
m:=1;
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;
        while (k shl 1<=m) do
                begin
                x:=k shl 1;
                if (x+1<=m) and (d[h[x+1]]<d[h[x]]) then
                                                        inc(X);
                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;
                        end
                        else break;
                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
                                if t[dir^[i]]=infi then begin
                                                 inc(m);
                                                 h[m]:=dir^[i];
                                                 poz[h[m]]:=m;
                                                 end;
                                d[dir^[i]]:=d[nod]+Cost^[i];
                                t[dir^[i]]:=nod;
                                k:=poz[dir^[i]];
                                while k>1 do
                                begin
                                x:=k shr 1;
                                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 break;
                                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]<>infi then write(d[i],' ')
                else write(0,' ');

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