#include <bits/stdc++.h>
using namespace std;
int son[102][2],f[50010];
int m,cnt,n,k;
int v[110],w[110],vv[110],ww[110];
vector<short>a[110];
signed main(){
	cin>>m>>cnt;
	int faa;
	for(int i=1;i<=cnt;i++){
		cin>>vv[i]>>ww[i]>>faa;
		ww[i]*=vv[i];
		if(faa){
			int kk=son[faa][1];
			n++;
			v[n]=vv[i]+v[faa];
			w[n]=ww[i]+w[faa];
			a[kk].push_back(n);
			if(son[faa][0]){
				n++;
				int bro=son[faa][0];
				v[n]=vv[i]+vv[bro]+vv[faa];
				w[n]=ww[i]+ww[bro]+ww[faa];
				a[kk].push_back(n);
			}
			else son[faa][0]=i;
		}
		else{
			n++;
			v[n]=vv[i],w[n]=ww[i];
			k++;
			son[i][1]=k;
			a[k].push_back(n);
		}
	}
//	for(int i=1;i<=n;i++)w[i]*=v[i];
	for(int i=1;i<=k;i++){
		for(int t=0;t<a[i].size();t++){
			int j=a[i][t];
			for(int l=m;l>=0;l--){
				if(l>=v[j])f[l]=max(f[l],f[l-v[j]]+w[j]);
			}
//			cout<<i<<" "<<j<<endl;
		}
//		cout<<endl;
	}
	cout<<f[m];
	return 0;
}