#include <bits/stdc++.h>
using namespace std;
int n, m;
int v[100000], p[600000], q[650000];
int dp[100000];
int vis[100000];

int main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		cin >> v[i] >> p[i] >> q[i];
	}
	for (int i = 1; i <= m; i++) {
		for (int j = n; j >= 0; j--) {
			if (q[i] == 0 && vis[i] == 0) {
				if (j >= v[i]) {
					int r;
					r = dp[j];
					dp[j] = max(dp[j], dp[j - v[i]] + v[i] * p[i]);
					if (dp[j] != r) {
						vis[i] = 1;
					}
				}
			} else {
				if (j >= v[i] + v[q[i]] && vis[q[i]] == 0) {
					int	r;
					r = dp[j];
					dp[j] = max(dp[j], dp[j - v[i] - v[q[i]]] + v[i] * p[i] + v[q[i]] * p[q[i]]);
					if (dp[j] != r) {
						vis[q[i]] = 1;
					}
				}
				if (j >= v[i] && vis[q[i]] == 1) {
					dp[j] = max(dp[j], dp[j - v[i]] + v[i] * p[i]);
				}
			}

		}
	}
	cout << dp[n];
	return 0;
}