#include <cstdlib>
#include <iostream>

using namespace std;
struct p
{
       int t,h,v;
}a[200];
int d,g,m,maxn,ans,maxd,die;
bool f[200][5000];
int cmp(const void *a,const void *b)
{
    p *aa=(p *)a;
    p *bb=(p *)b;
    if (aa->t>bb->t) return 1;
    return -1;
}
void readdata()
{
     int i,j;
     m=0;
     maxn=10;
     memset(a,0,sizeof(a));
     maxd=0;
     for (i=1;i<=g;i++)
     {
         scanf("%d %d %d\n",&a[i].t,&a[i].v,&a[i].h);
         maxn+=a[i].v;
     }    
     qsort(&a[1],g,sizeof(a[0]),cmp);
}
void dp()
{
     int i,j,k,now,t;
     bool have;
     memset(f,0,sizeof(f));
     f[0][10]=1;
     ans=0x7fffffff;
     die=0;
   
     for (k=1;k<=g;k++)
     {
         for (i=d;i>=0;i--)
            for (j=maxn;j>=0;j--)
            if ((j-a[k].t>=0)&&(f[i][j]))
            {
                if (i+a[k].h>=d)
                {
                    printf("%d\n",a[k].t);
                    return ;
                }
                f[i][j+a[k].v]=1;
                f[i+a[k].h][j]=1;
                f[i][j]=0;
            }
     }
     now=10;
     t=0;
     for (i=1;i<=g;i++)
     {
         if ((a[i].t-t)<=now)
         {
             now-=(a[i].t-t);
             now+=a[i].v;
             t=a[i].t;
         }
     }
     t+=now;
     if (ans<10000000) printf("%d\n",ans);
     else printf("%d\n",t);
}
int main(int argc, char *argv[])
{
    freopen("cow.in","r",stdin);
    freopen("cow.out","w",stdout);
    while (scanf("%d %d\n",&d,&g)!=EOF)
    {
        readdata();
        dp();
    }
    return 0;
}