#include <cstdio>
#include <iostream>
using namespace std;
int D;//井戸の深さ
int G;//ごみの数
class GOMI
{
public:
	int T;//ゴミは、時間の井戸に投げ込まれた
	int F;//生命を維持するために時間の無駄
	int H;//ゴミはの高さを高めることができる
}LJ[101];

int A[1001][101];
long long live=10; //卡門能活的最多時間

int Compare ( const void *a , const void *b )
{
	return *(int *)a - *(int *)b;
}

void init()
{
	for (int i=0;i<=1000;i++)
		for (int j=0;j<=100;j++)
			A[i][j]=0;
			
	cin>>D>>G;
	for (int i=1;i<=G;i++)
		cin>>LJ[i].T>>LJ[i].F>>LJ[i].H;
	
	qsort(LJ+1,G,sizeof(GOMI),Compare);
	
	for (int i=1;i<=G;i++)
		live+=LJ[i].F;
}

void dp()
{
	A[0][10]=1;
	for (int i=1;i<=G;i++)
	{
		//for (int j=0;j<=D-1;j++)
		for (int j=D-1;j>=0;j--)
		{
			//for (int k>=LJ[i].T;k++)
			for (int k=live;k>=LJ[i].T;k--)
			{
				if (A[j][k]>0)
				{
					A[j][k+LJ[i].F]++;//吃，不墊高
					A[j+LJ[i].H][k]++; //不吃，墊高
					if (j+LJ[i].H >=D)
					{
						cout<<LJ[i].T<<endl;
						return;
					}
				}
			}
		}
	}

}

int main()
{
	freopen("well.in","r",stdin);
	freopen("well.out","w",stdout);
	init();
	dp();
	return 0;
}