rt

// Problem: P1156 垃圾陷阱
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1156
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define F(i,j,k) for (signed i=signed(j);i<=signed(k);i++)
#define endl '\n'
//#define int long long
struct node{
	int t,f,h,sum;
}a[105];
int d,g,dp[105][100000];
main() { 
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>d>>g;
	F(i,1,g) cin>>a[i].t>>a[i].f>>a[i].h;
	sort(a+1,a+1+g,[](auto n1,auto n2){return n1.t<n2.t;});
	F(i,1,g) a[i].sum=a[i-1].sum+a[i].f;
	memset(dp,-1,sizeof dp);
	dp[0][10]=0;
	F(i,1,g){
		F(j,a[i].t,a[i].sum+10) {
			if(j>=a[i].f) dp[i][j]=max(dp[i][j],dp[i-1][j-a[i].f]);
			if(dp[i-1][j]!=-1) dp[i][j]=max(dp[i][j],dp[i-1][j]+a[i].h);
			if(dp[i][j]>=d) cout<<a[i].t<<endl,exit(0);
		}
	}
	cout<<a[g].sum+10<<endl;
	return 0; 
}