#include <bits/stdc++.h>
#define MAXM 65
#define MAXN 32005
#define child c[t[i]][k]
using namespace std;
int m, n, top;
long long w[MAXM], v[MAXM], dp[MAXN];
int t[MAXM];
vector<int> c[MAXM];
int main() {
	cin >> n >> m;
	for(int i = 1; i <= m; i++) {
		int f;
		cin >> w[i] >> v[i] >> f;
		if(!f)
			t[top++] = i;
		else
			c[f].push_back(i);
	}
	for(int i = 0; i < top; i++)
		for(int j = n; j >= w[t[i]]; j--) {
			if(j-w[t[i]] >= 0) {
				dp[j] = max(dp[j], dp[j-w[t[i]]]+w[t[i]]*v[t[i]]);
				for(int k = 0; k < c[t[i]].size(); k++)
					if(j-w[t[i]]-w[child] >= 0)
						dp[j] = max(dp[j], dp[j-w[child]]+w[child]*v[child]);
				if(c[t[i]].size() == 2 && j-w[t[i]]-w[c[t[i]][0]]-w[c[t[i]][1]] >= 0)
					dp[j] = max(dp[j], dp[j-w[t[i]]-w[c[t[i]][0]]-w[c[t[i]][1]]]+w[c[t[i]][0]]*v[c[t[i]][0]]+w[c[t[i]][1]]*v[c[t[i]][1]]);
						
			}
		}
	cout << dp[n];
	return 0;
}