#include <bits/stdc++.h>
using namespace std;
struct NODE
{
	//下落时间 
	int t;
	//堆的高度 
	int f;
	//吃的时间 
	int h;
	bool operator < (const NODE &x) const { return t<x.t; }
};
int h,n;
//辣鸡
NODE a[105];
//能不能出去 
bool flag = false;
//能出去:最短的出去时间 
int mim = 0x3f3f3f3f;
//不能出去:最长的存活时间 
int mam = -mim;
/*
tf[a][b][c]:
	在第a个辣鸡,还有b能量,高度为c时已经出现过 
*/
bool tf[105][105][3005];
/*
1. x:
	当前是第几个辣鸡 
2. time：
	还有多少能量 
3. height：
	当前的高度
*/
void AAA(int x,int time,int high)
{
	//这个情况已经出现过了
	if(tf[x][time][high]) return;
	//标记这个情况已经出现过了
	tf[x][time][high] = true;
	//后面再没辣鸡了
	if(x>n+1) return;
	//还有多少能量减去等待时间
	if(time>=a[x].t-a[x-1].t) time -= (a[x].t-a[x-1].t);
	else
	{
		//还没等到辣鸡下落就挂了
		//不能出去:更新最长的存活时间
		mam = max(mam,a[x-1].t+time);
		/*
		max(mam,a[x-1].t+time):
			1.mam:最长的存活时间
			2.a[x-1].t+time:上一个辣鸡下落的时间加上还有多少能量 
		*/
		//返回 
		return; 
	}
	//把这个辣鸡堆了能不能出去 
	if(high+a[x].f>=h)
	{
		//把这个辣鸡堆了能出去
		flag = true;
		//能出去:更新最短的出去时间 
		mim = min(mim,a[x].t);
		/*
		min(mim,a[x].t):
			1.mim:最短的出去时间
			2.a[x].t:当前辣鸡下落的时间 
		*/
		//返回
		return;
	}
	//堆 
	AAA(x+1,time,high+a[x].f); 
	//吃
	AAA(x+1,time+a[x].t,high); 
}
int main()
{
	//输入 
	cin>>h>>n;
	for(int i=1;i<=n;i++) cin>>a[i].t>>a[i].f>>a[i].h;
	//排序	
	sort(a+1,a+1+n);
	//第0个辣鸡在0时间落下 
	a[0].t = 0;
	//第n+1个辣鸡在无限时间落下 
    a[n+1].t = 0x3f3f3f3f;
    AAA(1,10,0); 
//	cout<<flag<<"\n";
    if(flag) cout<<mim;
    else cout<<mam;
	return 0;
}