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

const int N=1010;
int d,n,f[N][10000];

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);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d%d",&t[i].t,&t[i].life,&t[i].h);
	}
	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=t[i+1].t;j<=10000;j++)
		{
			f[i+1][j]=max(f[i+1][j],f[i][j]+t[i+1].h);
			f[i+1][j+t[i+1].life]=max(f[i+1][j+t[i+1].life],f[i][j]);
			if(f[i][j]>=d)
			{
				cout<<t[i].t;
				return 0;
			}
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		ans+=t[i].life;
	}
	cout<<ans;
	return 0;
}