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

int d,g,ans1,ans2,f[105][3005];

struct laji{
	int t,F,h;
}lj[105];

bool cmp(const laji x,const laji y)
{
	return x.t<y.t;
}

int main()
{
	for(int j=0;j<=100;j++)
	for(int i=0;i<=3000;i++)f[j][i]=-900;
	cin>>d>>g;
	f[0][10]=0;
	for(int i=1;i<=g;i++)
	{
		cin>>lj[i].t>>lj[i].F>>lj[i].h;
		ans2+=lj[i].F;
	}
	sort(lj+1,lj+1+g,cmp);
	for(int i=1;i<=g;i++)
	{
		for(int j=3500;j>=lj[i].t;j--)
		{
			f[i][j]=max(f[i][j],f[i-1][j]+lj[i].h);//use
			if(j>lj[i].F)
			f[i][j]=max(f[i][j],f[i-1][j-lj[i].F]);//eat
			if(f[i][j]>=d){ans1=lj[i].t;break;}
		}
		if(ans1)break;
	}
	if(ans1)cout<<ans1;
	else cout<<10+ans2;
	return 0;
}

f[i][j]是到第i个物品生命值为j时的高度最大值