#include<iostream>
#include<stdio.h>//freopen
#include<string.h>//网上说加的！！
#include<cstdlib>//不知道是神马！
#include<stdlib.h>//快排必加！！
using namespace std;
int cmp(const void *a,const void *b);
int MAX=0;
bool q[210][5100];
int number,longth;//长度，个数
struct hehe
{
	int t,h,l;//时间，补得血，长度
}a[200];
void dp();//DP
int main()
{
	freopen ("well.in","r",stdin);
	freopen ("well.out","w",stdout);
	scanf("%d %d",&longth,&number);
	for (int i=0;i<number;i++)
	{
		scanf("%d %d %d\n",&a[i].t,&a[i].h,&a[i].l);
		MAX+=a[i].h;//求出最大可能的时间数，我感觉应该加10
	}
	MAX+=10;
	qsort(&a[1],number,sizeof(a[0]),cmp);//快排，看老师的，小不懂！
	dp();
}
int cmp(const void *a,const void *b)
{
	return ((hehe *)a)->t > ((hehe *)b)->t ? 1 : -1;//真不懂！
}
void dp()
{
	int answer=0;//有无结果的标志！
	q[0][10]=true;//因为开始有10小时的生命值，所以，在0位置，10生命值时为TRUE！！
	for (int i=0;i<number;i++)
	{
		if (answer)//不解释！
		{
			break;
		}
		for (int j=longth;j>=0;j--)
		{
			if (answer)//不解释！！
			{
				break;
			}
			for (int k=MAX;k>=0;k--)
			{
				if (answer)//不解释！！
				{
					break;
				}
				if (k-a[i].t>=0&&q[j][k])//如果能等到垃圾掉到地上，且这一点可以的话,就执行！
				{
					if (k+a[i].l>=longth)//应该先判断，我开始没先判断，吃亏呀，水呀，湿透了，哎呀，hot!!!
					{
						cout<<k;
						answer++;
					}
					q[j+a[i].l][k]=true;//如果这一点行的话，那么，下一块垃圾是让他吃，还是踩那？？？？？吃还是踩这是个问题！！！！
					q[j][k+a[i].h]=true;//恩，不如都试试！呵呵呵呵呵呵呵！
					q[i][j]=false;//那么这一点就作废了！哎！
				}
			}
		}
	}
	if (!answer)//没找到答案的时候！
	{
		int ji=10;//开始有10的HP；
		for (int i=0;i<number;i++)
		{
			if (ji-a[i].l)//判断在垃圾掉下之前能活不！
			{
				ji=ji-a[i].l+a[i].h;
			}
		}
		cout<<ji;
	}
}
//PaulInsider（huenze）注释，编写，任何人转载请注意版权，呵呵呵呵！！
//胡恩泽（版权在手，天地任我游）！！
//我看行！！