#include<bits/stdc++.h>
using namespace std;
const int MAXN = 3.2* 10000 + 5,MAXM = 65;
int n,m;
int f[MAXN];
int cnt[MAXM],w[MAXM],v[MAXM];
int t[MAXM][MAXM];
int al[MAXM];
int main(){
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= m;i++){
		int k;
		scanf("%d%d%d",&w[i],&v[i],&k);
		if(k!=0) al[i]++,cnt[k]++;t[k][cnt[k]] = i;
	}
	for(int i = 1;i <= m;i++){
	if(al[i] != 0) continue;
	for(int j = n;j >= w[i];j--){
		f[j] = max(f[j],f[j-w[i]]+w[i]*v[i]);
		if((w[i] + w[t[i][1]]) <= j) f[j] = max(f[j],f[j-w[i]-w[t[i][1]]] +w[t[i][1]]*v[t[i][1]]+w[i]*v[i]);
		if((w[i] + w[t[i][2]]) <= j) f[j] = max(f[j],f[j-w[i]-w[t[i][2]]] +w[t[i][2]]*v[t[i][1]]+w[i]*v[i]);
	    if((w[i] + w[t[i][1]] + w[t[i][2]]) <= j) f[j] = max(f[j],f[j-w[i]-w[t[i][1]] - w[t[i][2]]] +w[t[i][2]]*v[t[i][2]] +w[t[i][1]]*v[t[i][1]]+w[i]*v[i]);
	}
	}
	printf("%d",f[n]);
	return 0;
}

不知道为什么测试点8不能通过，有好心人分享下测试点8的数据嘛。