#include <bits/stdc++.h>
using namespace std;
const int MAXT = 60 + 10;
const int MAXN = 60 + 10;
const int MAXV = 32000 + 10;
int c[MAXT][MAXN], w[MAXT][MAXN];
int dp[MAXV];
int v, n, t;
int main()
{
	cin >> v >> n;
	memset(c, 0, sizeof(c));
	memset(w, 0, sizeof(w));
	for (int i = 1; i <= n; i++)
	{
		int cc, ww, pp;
		cin >> cc >> ww >> pp;
		if (pp == 0)
		{
			c[i][0]++;
			c[i][c[i][0]] = cc;
			w[i][0]++;
			w[i][w[i][0]] = ww*cc;
		}
		else
		{
			c[pp][0]++;
			c[pp][c[pp][0]] = cc;
			w[pp][0]++;
			w[pp][w[pp][0]] = ww*cc;
		}
	}
	memset(dp, 0, sizeof(dp));
	for (int i = 1; i <= n; i++)
		if (c[i][0])
		{
			if(c[i][0]==2){
				c[i][2]+=c[i][1];
				w[i][2]+=w[i][1];
			}else if(c[i][0]==3){
				c[i][0]++;
				c[i][4]=c[i][1]+c[i][2]+c[i][3];
				w[i][0]++;
				w[i][4]=w[i][1]+w[i][2]+w[i][3];
				c[i][2]+=c[i][1];
				w[i][2]+=w[i][1];
				c[i][3]+=c[i][1];
				w[i][3]+=w[i][1];
			}
			for (int j = v; j >= 0; j--)
				for (int k = 1; k <= c[i][0]; k++)
					if (j >= c[i][k])
						dp[j] = max(dp[j], dp[j - c[i][k]] + w[i][k]);
		}
	cout << dp[v] << endl;
	return 0;
}