const infinit=1000000000;
type graf=record x,y,k:longint;end;
var t:array[1..250000]of graf;
    d:array[1..50000]of longint;
    v:array[1..50000]of byte;
    tt:array[1..50000]of word;
    x,n,m,i,j,k,min:longint;
    ok:boolean;
function pozitie(p,u:longint):longint;
var piv,aux:graf;
begin
 piv:=t[p];
 while p<u do
  begin
   if (t[p].x>t[u].x)or(t[p].x=t[u].x)and(t[p].y>t[u].y) then begin aux:=t[p];t[p]:=t[u];t[u]:=aux;end;
   if (piv.x=t[p].x)and(piv.y=t[p].y) then u:=u-1 else p:=p+1;
  end;
 pozitie:=p;
end;
procedure sort(p,u:longint);
var k:longint;
begin
 if p<u then
         begin
          k:=pozitie(p,u);
          sort(p,k-1);
          sort(k+1,u);
         end;
end;
function cost(x,y:integer):longint;
var p,u,k:longint;
begin
 p:=1;
 u:=m;
 while p<=u do
  begin
   k:=(p+u)div 2;
   if t[k].x>=x then u:=k-1
                else p:=k+1;
  end;
 j:=p;
 while (j<=m)and(t[j].x=x)and(t[j].y<y) do j:=j+1;
 if (j<=m)and(t[j].x=x)and(t[j].y=y) then cost:=t[j].k
                                     else cost:=infinit;
end;
begin
 assign(input,'dijkstra.in');
 reset(input);
  readln(n,m);
  for i:=1 to m do
   readln(t[i].x,t[i].y,t[i].k);
 close(input);

  sort(1,m);
  for i:=1 to n do
   begin
    v[i]:=0;
    tt[i]:=1;
    j:=1;
    while(t[j].x=1)and(t[j].y<i)and(j<=m) do j:=j+1;
    if(j<=m)and(t[j].x=1)and(t[j].y=i) then d[i]:=t[j].k
                                       else d[i]:=infinit;
   end;
  ok:=true;
  v[1]:=1;
  tt[1]:=0;
  while ok do
   begin
    min:=infinit;
    for i:=1 to n do
     if (v[i]=0)and(d[i]<min) then begin min:=d[i];k:=i;end;
    if min<>infinit then
                        begin
                         v[k]:=1;
                         for i:=1 to n do
                          if (v[i]=0)and(d[i]>d[k]+cost(k,i)) then
                                                               begin
                                                                d[i]:=d[k]+cost(k,i);
                                                                tt[i]:=k;
                                                               end;
                        end
                         else ok:=false;
   end;

 assign(output,'dijkstra.out');
 rewrite(output);
  write(d[2]);
  for i:=3 to n do write(' ',d[i]);
 close(output);
end.