#include<bits/stdc++.h>
using namespace std;
struct Stu {
	int t,f,h;
} a[100+10];
int d[100+10];
bool cmp(const Stu &a,const Stu b) {
	return a.t<b.t;
}
int main() {
	int D,g;
	cin>>D>>g;
	for(int i=1; i<=g; i++) {
		cin>>a[i].t>>a[i].f>>a[i].h;
	}
	sort(a+1,a+g+1,cmp);
	d[0]=10;
	for(int i=1; i<=g; i++) {
		for(int j=D; j>=0; j--) {
			if(d[j]>=a[i].t) {
				if(j+a[i].h>=D) {
					cout<<a[i].t;
					return 0;
				}
				d[j]+=a[i].f;
			}
			if(j>=a[i].h&&d[j-a[i].h]>=a[i].t){
				if(j>=D) {
					cout<<a[i].t;
					return 0;
				}
				d[j]=d[j-a[i].h];
			}
		}
	}
	cout<<d[0];
	return 0;
}