type vec=array[1..250001] of longint;
var h,d,t,u:array[0..50001] of longint;
x,poz:array[0..50001]of longint;
n,i,j,k,l,m,nh,nod:longint;
dir,c:^vec;
a,b,ci:array[0..250001] of longint;

procedure swap(i,j:longint);
var T:longint;
begin
t:=h[i]; h[i]:=h[j]; h[j]:=t;
poz[h[i]]:=i; poz[h[j]]:=j;
end;

procedure Heapdw(r,k:longint);
var st,dr,i:longint;
begin
 if 2*r+1<=k then
        begin
        st:=h[2*r+1];
        if 2*r+2<=k then
        dr:=h[2*r+2]
        else dr:=st-1;
 if st>dr then i:=2*r+1
 else i:=2*r+2;
 if d[h[r]]>d[h[i]] then
 begin
 swap(i,r);heapdw(i,k);
end;    end;end;

procedure heapup(k:longint);
var t:integer;
begin
if k>0 then
begin
t:=(k-1) div 2;
if d[h[k]]<d[h[t]] then begin
        swap(k,t);heapup(T);
end;
end;
end;

procedure buildh(k:longint);
begin
for i:=1 to  k-1 do heapup(I);
end;

function scoate_heap:longint;
begin
swap(0,nh-1);
poz[h[nh-1]]:=0; dec(nh);
heapdw(0,nh-1);
scoate_heap:=h[nh];
end;


procedure dijkstra(sursa:longint);
var i,nod:longint;
begin
fillchar(u,sizeof(u),0);
fillchar(t,sizeof(t),0);
fillchar(d,sizeof(d),63);
for i:=0 to n-1 do
        begin
        poz[i+1]:=i;
        h[i]:=i+1;
        end;
d[sursa]:=0;
buildh(N);nh:=n;
while nH>0 do
begin
nod:=scoate_heap;
for i:=x[nod]+1 to x[nod+1] do
        if d[dir^[i]]>d[nod]+c^[i] then
                begin
                d[dir^[i]]:=d[nod]+c^[i];
                t[dir^[i]]:=nod;
                heapup(poz[dir^[i]]);
                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
                read(a[i]);
                read(b[i]);
                read(ci[i]);
                inc(x[a[i]]);
                 end;
for i:=2 to n do x[i]:=x[i]+x[i-1];
x[n+1]:=x[n];
new(Dir);
new(c);
for i:=1 to m do
        begin
        dir^[x[a[i]]]:=b[i];
        c^[x[a[i]]]:=ci[i];
        dec(x[a[i]]);
        end;
dijkstra(1);
for i:=2 to n do if d[i]<1061109567 then write(d[i],' ')
                else write(0,' ');
close(input);
close(output);
end.