#include<bits/stdc++.h>
using namespace std;
long long dp[70][32010] , v[70] , w[70] , f[70][2];
int mm[70];
bool s[70];

int main(){
	int n , m;
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		int x;
		cin >> v[i] >> w[i] >> x; 
		if(x != 0){
			f[x][mm[x]++] = i;
			s[i] = true;
		}
	}
	for(int i = 0; i <= n; i++){
		for(int j = 1; j <= m; j++){
			if(s[j]) continue;
			if(mm[j] == 0){
				if(v[j] > i) dp[j][i] = dp[j - 1][i];
				else dp[j][i] = max(dp[j - 1][i] , dp[j - 1][i - v[j]] + v[j] * w[j]);
			}else if(mm[j] == 1){
				if(v[j] > i) dp[j][i] = dp[j - 1][i];
				else if(v[j] + v[f[j][0]] > i) dp[j][i] = max(dp[j - 1][i] , dp[j - 1][i - v[j]] + v[j] * w[j]);
				else dp[j][i] = max({dp[j - 1][i] , dp[j - 1][i - v[j]] + v[j] * w[j] , dp[j - 1][i - v[j] - v[f[j][0]]] + v[j] * w[j] + v[f[j][0]] * w[f[j][0]]}); 
			}else{
				if(v[j] > i) dp[j][i] = dp[j - 1][i];
				else if(v[j] <= i && v[j] + v[f[j][0]] > i && v[j] + v[f[j][1]] > i) dp[j][i] = max(dp[j - 1][i] , dp[j - 1][i - v[j]] + v[j] * w[j]);
				else if(v[j] + v[f[j][0]] > i && v[j] + v[f[j][1]] <= i) dp[j][i] = max({dp[j - 1][i] , dp[j - 1][i - v[j]] + v[j] * w[j] , dp[j - 1][i - v[j] - v[f[j][1]]] + v[j] * w[j] + v[f[j][1]] * w[f[j][1]]}); 
				else if(v[j] + v[f[j][0]] <= i && v[j] + v[f[j][1]] > i) dp[j][i] = max({dp[j - 1][i] , dp[j - 1][i - v[j]] + v[j] * w[j] , dp[j - 1][i - v[j] - v[f[j][0]]] + v[j] * w[j] + v[f[j][0]] * w[f[j][0]]}); 
				else if(v[j] + v[f[j][0]] + v[f[j][1]] > i) dp[j][i] = max({dp[j - 1][i] , dp[j - 1][i - v[j]] + v[j] * w[j] , dp[j - 1][i - v[j] - v[f[j][0]]] + v[j] * w[j] + v[f[j][0]] * w[f[j][0]] , dp[j - 1][i - v[j] - v[f[j][1]]] + v[j] * w[j] + v[f[j][1]] * w[f[j][1]]});
				else dp[j][i] = max({dp[j - 1][i] , dp[j - 1][i - v[j]] + v[j] * w[j] , dp[j - 1][i - v[j] - v[f[j][0]]] + v[j] * w[j] + v[f[j][0]] * w[f[j][0]] , dp[j - 1][i - v[j] - v[f[j][1]]] + v[j] * w[j] + v[f[j][1]] * w[f[j][1]] , dp[j - 1][i - v[j] - v[f[j][0]] - v[f[j][1]]] + v[j] * w[j] + v[f[j][0]] * w[f[j][0]] + v[f[j][1]] * w[f[j][1]]});
			}
		}
	}
	cout << dp[m][n];
	return 0;
}