#include<bits/stdc++.h>
using namespace std;
int n,m,sn,fn,zz[1000000];
struct fj
{
	int money;
	int score;
}f[1000];
struct m
{
	int money;
	int score;
	vector <int> ff; 
}s[1000];
int main()
{
	cin>>n>>m;
	for (int i=1;i<=m;i++)
	{
		int la,lb,lc;
		cin>>la>>lb>>lc;
		if (lc!=0)
		{
			fn++;
			f[fn].score=lb*la;
			f[fn].money=la;
			s[lc].ff.push_back(fn);
		}
		else
		{
			sn++;
			s[sn].money=la;
			s[sn].score=lb*la;
		}
	}
	for (int i=1;i<=sn;i++)
	{
		if (s[i].ff.size()==2) 
		{
			fn++;
			f[fn].money=f[s[i].ff[1]].money+f[s[i].ff[0]].money;
			f[fn].score=f[s[i].ff[1]].score+f[s[i].ff[0]].score;
			s[i].ff.push_back(fn);
		}
	}
	for (int i=1;i<=sn;i++)
	{
		int l=s[i].ff.size();
		int ls0=s[i].score,lm0=s[i].money,ls1,lm1,ls2,lm2,ls3,lm3;
		if (l>=1) ls1=ls0+f[s[i].ff[0]].score,lm1=lm0+f[s[i].ff[0]].money;
		if (l==3) ls2=ls0+f[s[i].ff[1]].score,lm2=lm0+f[s[i].ff[1]].money,ls3=ls0+f[s[i].ff[2]].score,lm3=lm0+f[s[i].ff[2]].money;
		for (int j=n;j>=lm0;j--) 
		{
			if (l>=0) zz[j]=max(zz[j],zz[j-lm0]+ls0);
			if (l>=1&&j>=lm1) zz[j]=max(zz[j],zz[j-lm1]+ls1);
			if (l==3&&j>=lm2) zz[j]=max(zz[j],zz[j-lm2]+ls2);
			if (l==3&&j>=lm3) zz[j]=max(zz[j],zz[j-lm3]+ls3);
		}
	}
	cout<<zz[n];
}
//2000 10
//500 1 0
//400 4 0
//300 5 1
//400 5 1
//200 5 0
//500 4 5
//400 4 0
//320 2 0
//410 3 0
//400 3 5
//
//7430