sort有毒！！！

var
d,g,i,j,maxx:longint;
t,h,f:array[0..201]of longint;
dp:array[0..201,0..3000]of longint;
procedure change(var a,b:longint);
var
p:longint;
begin
 p:=a;
 a:=b;
 a:=p;
end;
procedure sort(l,r:longint);
var
i,j,mid,p:longint;
begin
 i:=l;
 j:=r;
 mid:=t[random(r-l+1)+l];
 repeat
  while t[i]<mid do inc(i);
  while t[j]>mid do dec(j);
  if i<=j then begin
   change(t[i],t[j]);change(f[i],f[j]);change(h[i],h[j]);
   inc(i);dec(j);
  end;
 until i>j;
 if i<r then sort(i,r);
 if l<j then sort(l,j);
end;
function max(a,b:longint):longint;
begin
 if a>b then exit(a)
  else exit(b);
end;
begin
 assign(input,'well.in');reset(input);
 assign(output,'well.out');rewrite(output);
 fillchar(dp,sizeof(dp),$ff);
 maxx:=10;
 readln(d,g);
 for i:=1 to g do
 begin
  readln(t[i],f[i],h[i]);
  inc(maxx,f[i]);
 end;
 sort(1,g);
 //for i:=1 to g do writeln(t[i],' ');
 dp[0,10]:=0;
 for i:=1 to g do
  for j:=t[i] to maxx do
   if(dp[i-1,j]<>-1) then
    begin
     dp[i,j+f[i]]:=dp[i-1,j];
     dp[i,j]:=max(dp[i,j],dp[i-1,j]+h[i]);
     if(dp[i][j]>=d)then
       begin
      write(t[i]);
close(input);close(output);
      halt;
    end;
    if(dp[i,j+f[i]]>=d) then
    begin
           write(t[i]);
close(input);close(output);
       halt;
    end;
     end;
maxx:=10;
for i:=1 to g do
    if(maxx>=t[i]) then inc(maxx,f[i]);
write(maxx);
close(input);close(output);
end.