1234

#include<bits/stdc++.h>
using namespace std;
struct node {
	int v;
	int w;
};
struct node2 {
	int vv,pp,qq,num;
} y[65];
vector<node>h[100];
int dp[32005];
bool cmp(node2 a,node2 b) {
	return a.qq<b.qq;
}
int main() {
	int n,m,i,j,k;
	int cnt=0;
	cin >> n >> m;
	for(i=1; i<=m; i++) {
		cin >> y[i].vv >> y[i].pp >> y[i].qq;
		y[i].num=i;
	}
	sort(y+1,y+m+1,cmp);
	for(i=1; i<=m; i++) {
		node x;
		if(y[i].qq==0) {
			x.v=y[i].vv;
			x.w=y[i].vv*y[i].pp;
			h[y[i].num].push_back(x);
		} else {
			int s=h[y[i].qq].size();
			for(j=0; j<s; j++) {
				x.v=y[i].vv+h[y[i].qq][j].v;
				x.w=y[i].vv*y[i].pp+h[y[i].qq][j].w;
				h[y[i].qq].push_back(x);
			}
		}
	}
	for(i=1; i<=m; i++) {
		if(h[i].size()==0) continue;
		for(j=n; j>=0; j--) {
			for(k=0; k<h[i].size(); k++) {
				if(h[i][k].v<=j) dp[j]=max(dp[j],dp[j-h[i][k].v]+h[i][k].w);
			}
		}
	}
	cout << dp[n];
	return 0;
}