#include<bits/stdc++.h>
using namespace std;
int dp[33900];
struct thing{
	int w;
	int v;
	int q;
	int fj1;
	int fj2;
}s[70];
int n,m;
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>s[i].w>>s[i].v>>s[i].q;
		if(s[i].q!=0){
			int to=s[i].q;
			if(s[to].fj1==0)s[to].fj1=i;
			else s[to].fj2=i;
		}//设置附件1,2
	}
	for(int i=1;i<=m;i++){
		if(s[i].q!=0)continue;
		for(int j=n;j>=s[i].w;j--)
		dp[j]=max(dp[j],dp[j-s[i].w]+s[i].w*s[i].v);//考虑一般情况
		if(s[i].fj1!=0){
			int abst=s[i].w+s[s[i].fj1].w,ret=s[i].fj1;
			for(int j=n;j>=abst;j--)
			dp[j]=max(dp[j],dp[j-abst]+s[i].w*s[i].v+s[ret].w*s[ret].v);//主+1
			if(s[i].fj2!=0){
				int uhj=s[i].w+s[s[i].fj2].w,rst=s[i].fj2;
				for(int j=n;j>=uhj;j--)
				dp[j]=max(dp[j],dp[j-uhj]+s[i].w*s[i].v+s[rst].w*s[rst].v);//主+2
				int mem=s[i].w+s[s[i].fj1].w+s[s[i].fj2].w;
				for(int j=n;j>=mem;j--)
				dp[j]=max(dp[j],dp[j-mem]+s[i].w*s[i].v+s[ret].w*s[ret].v+s[rst].w*s[rst].v);//主+1+2
			}
		}
	}
	cout<<dp[n];
}