#include <cstdlib>
#include <iostream>
#include <cstdio>

using namespace std;

int i,j,k,d,g,live,ans;
int t[101],h[101],l[101];
int f[101][3001];

int main()
{
	freopen("well.in","r",stdin);
	freopen("well.out","w",stdout);
	scanf("%d%d\n",&d,&g);
	for (i=1;i<=g;i++)
	{
		scanf("%d%d%d\n",&t[i],&l[i],&h[i]);
		ans+=l[i];
	}
	memset(f,-1,sizeof(f));
	live=10;
	f[0][10]=0;
	for (i=1;i<=g;i++)
	{
		for (j=0;j<=live;j++)
			for (k=0;k<=i-1;k++)
			{
				if (f[k][j+t[i]-t[k]]>-1)
				{
					f[i][j]=f[k][j+t[i]-t[k]]+h[i];
					f[i][j+l[i]]=f[k][j+t[i]-t[k]];
					if (f[i][j]>=d)
					{
						ans=t[i];
						goto fuck;
					}				
				}
			}
		live+=l[i];
	}
	fuck:
	printf("%d\n",ans);
	return 0;
}