#include<bits/stdc++.h>
#define int long long
int n,w,f[100005];
struct node{
	int jv,v,w,m,zhujiannum;
	bool b=0;
}a[100005];
using namespace std;
signed main()
{
	cin>>w>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].jv>>a[i].w>>a[i].m;
		a[i].v=a[i].jv*a[i].w;
		if(a[i].m==0)	a[i].zhujiannum=a[i].jv;
	}
	for(int i=1;i<=n;i++)
	{
		if(a[i].m==0)
			continue;
		else if(a[a[i].m].b==0)
		{
			a[a[i].m].zhujiannum+=a[i].jv;
			a[i].v+=a[a[i].m].v,a[i].jv+=a[a[i].m].jv;
			a[a[i].m].b=1;
			
		}
		else
			a[i].jv+=a[a[i].m].zhujiannum;
	}
//	for(int i=1;i<=n;i++)
//	{
//		cout<<a[i].jv<<' '<<a[i].v<<' '<<a[i].w<<' '<<a[i].m<<' '<<a[i].b<<' '<<a[i].zhujiannum<<endl;
//	}
	for(int i=1;i<=n;i++)
		for(int j=w;j>=a[i].jv;j--)
			f[j]=max(f[j],f[j-a[i].jv]+a[i].v);
	cout<<f[w];
	return 0;
}