#include<bits/stdc++.h>
using namespace std;

const int N=105;
int d,n,f[N][3010];

struct T
{
	int t,life,h;
}t[N];

bool cmp(T a,T b)
{
	return a.t<b.t;
}

int main()
{
	scanf("%d%d",&d,&n);
	int sum=0;
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d%d",&t[i].t,&t[i].life,&t[i].h);
		sum+=t[i].life;
	}
	sort(t+1,t+1+n,cmp);
	memset(f,128,sizeof f);
	f[0][10]=0;
	for(int i=0;i<=n;i++)
	{
		for(int j=10;j<=sum;j++)
		{
			if(f[i][j]<-1e9||j<t[i].t)continue;
			f[i+1][j+t[i+1].life]=max(f[i+1][j+t[i+1].life],f[i][j]);
			f[i+1][j]=max(f[i+1][j],f[i][j]+t[i+1].h);
			if(f[i][j]>=d)
			{
				cout<<t[i].t;
				return 0;
			}
		}
	}
	cout<<sum;
	return 0;
}