#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

#define int long long

const int maxn = 105;

int d, g, m;
// m: sum of f[i]

struct I {
	int t, f, h;
} rbs[maxn];

/*
 *	compare type I
*/
bool cmp(const I& _a, const I& _b) {
	return _a.t < _b.t;
}

int dp[maxn][3005];
/*
 *	dp[i][j](i压维):
 *		i: 前i个物品（按时间排顺序）,
 *		j: 存活到第j秒,
 *		最高的高度
 *	更新:
 *		dp[j] += h[i]; (j >= t[i])
 *		dp[j] = max(dp[j], dp[j - f[i]]); (j - f[i] >= t[i])
*/

signed main() {
	cin >> d >> g;
	for (int i = 1; i <= g; i++) {
		cin >> rbs[i].t >> rbs[i].f >> rbs[i].h;
		m += rbs[i].f;
	}
	sort(rbs + 1, rbs + g + 1, cmp);
stop1:
	memset(dp, 0x80, sizeof(dp));
	for (int i = 0; i <= 10; i++) {
		dp[0][i] = 0;
	}
//	dp[0][10] = 0;
	for (int i = 1; i <= g; i++) {
		for (int j = 0; j <= m; j++) {
			if (j - rbs[i].f >= rbs[i].t) {
				dp[i][j] = max(dp[i][j], dp[i - 1][j - rbs[i].f]);
			}
			if (j >= rbs[i].t) {
				dp[i][j] = max(dp[i][j], dp[i - 1][j] + rbs[i].h);
			}
			if (dp[i][j] >= d) {
				cout << rbs[i].t << endl;
				return 0;
			}
		}
	}
	cout << m << endl;
}