#include <bits/stdc++.h>
using namespace std;
int n,m,ans=INT_MAX;
map<int,int>q[2005][2005];
struct node {
	int t,h,f;
} a[1005];
bool cmp(node x,node y) {
	return x.t<y.t;
}
void dfs(int id,int hi,int he,int ti) {
	if(q[hi][he][ti]==1)return;
	q[hi][he][ti]=1;
	if(hi>=m) {
		ans=min(ans,ti);
		return;
	}
	if(id>n) {
		return;
	}
	if(a[id].t>he)return;
	dfs(id+1,hi,he+a[id].f,a[id].t);
	if(he<a[id+1].t)return;
	dfs(id+1,hi+a[id].h,he,a[id].t);
	return;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>m>>n;
	int sum=0;
	for(int i=1; i<=n; i++) {
		cin>>a[i].t>>a[i].f>>a[i].h;
		sum+=a[i].f;
	}
	int hel=10;
	sort(a+1,a+n+1,cmp);
	for(int i=1; i<=n; i++) {
		if(a[i].t>hel) {
			cout<<hel;
			return 0;
		}
		hel+=a[i].f;
	}
	dfs(1,0,10,a[1].t);
	if(ans==INT_MAX) {
		int hel=10;
		for(int i=1; i<=n; i++) {
			if(a[i].t>hel) {
				cout<<hel;
				return 0;
			}
			hel+=a[i].f;
		}
		cout<<hel;
	} else {
		cout<<ans;
	}
	return 0;
}