#include<bits/stdc++.h>
using namespace std;
#define rint register int
#define rep(i,s,t) for(rint i=s;i<=t;i++)
#define per(i,s,t) for(rint i=s;i>=t;i--)
#define INF 0x3f3f3f3f
#define NEG_INF 0xc0c0c0c0

//---
// #define FILE
// #define DEBUG
// #define TIME
//---
const int MAX = 100+5;
struct Garbage{
    int t,f,h;
    Garbage(int t=0,int f=0,int h=0):t(t),f(f),h(h){}
    friend bool operator<(Garbage a,Garbage b){
        return a.t<b.t;
    }
}A[MAX];
int d,g,life=10;
int min_time=INF,max_time=0;
inline void getint(int &x){
    x=0;
    char c = getchar();
    while(c<'0'||'9'<c)c=getchar();
    while('0'<=c&&c<='9')
        x=(x<<1)+(x<<3)+c-'0',
        c=getchar();
}
inline void getint(short &x){
    x=0;
    char c = getchar();
    while(c<'0'||'9'<c)c=getchar();
    while('0'<=c&&c<='9')
        x=(x<<1)+(x<<3)+c-'0',
        c=getchar();
}
inline int min(int a,int b){return a<b?a:b;}
inline int max(int a,int b){return a>b?a:b;}
void dfs(int idx,int life,int height){
    if(A[idx-1].t>=min_time) return;
    if(height>=d){//D!=0
        min_time=min(min_time,A[idx-1].t);
        return;
    }
    if(A[idx].t>life||idx>g){
        max_time=max(max_time,life);
        return;
    }
    dfs(idx+1,life+A[idx].f,height);
    dfs(idx+1,life,height+A[idx].h);
}
int bad_solution(){
    dfs(1,10,0);
    if(min_time!=INF) return min_time;
    else return max_time;
}

int dp[MAX][2000];//garbage, life
bool vis[MAX][2000];
int solution(){
    vis[0][10]=1;
    int maxn,minn,tpmaxn,tpminn;
    tpmaxn=tpminn=10;
    for(int i=1;i<=g;i++){
        int delta = A[i].t-A[i-1].t;
        bool flag=1;
        maxn=tpmaxn,minn=tpminn;
        for(int j=max(minn-delta,0);j<=maxn-delta+A[i].f;j++){
            if(vis[i-1][j+delta]){
                dp[i][j]=max(dp[i][j],dp[i-1][j+delta]+A[i].h);
                vis[i][j]=1;
            }
            if(j-A[i].f>=0 && vis[i-1][j+delta-A[i].f]){
                dp[i][j]=max(dp[i][j],dp[i-1][j+delta-A[i].f]);
                vis[i][j]=1;
            }
            if(vis[i][j]){
                if(flag)
                    tpminn=j,flag=0;
                tpmaxn=j;
                if(dp[i][j]>=d){
                    return A[i].t;
                }
            }
        }
        if(flag)break;
    }
    int life = 10;
    for(int i=1;i<=g;i++){
        if(life<A[i].t) break;
        life+=A[i].f;
    }
    return life;
}
int main(){
#ifdef TIME
    clock_t start_time = clock();
#endif
#ifdef FILE
    freopen("r.in","r",stdin);
    // freopen("","w",stdout);
#endif

    getint(d),getint(g);
    rep(i,1,g) getint(A[i].t),getint(A[i].f),getint(A[i].h);
    sort(A+1,A+1+g);//可能归并快//g<=100没必要
    printf("%d\n",solution());

#ifdef DEBUG
    printf("%d\n",bad_solution());
#endif
#ifdef FILE
    fclose(stdin);
    // fclose(stdout);
#endif
#ifdef TIME
    printf("%.2f sec\n",(clock()-start_time)/1000.0);
#endif

    return 0;
}