#include<bits/stdc++.h>
using namespace std;

int n,m,ap[62][32100],v[62],p[62],mas[62];

int main(){
	cin >> n >> m;
	
	for(int i=1;i<=m;i++){
		cin >> v[i] >> p[i] >> mas[i];
	}
	
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			ap[i][j]=max(ap[i][j],ap[i-1][j]);
			if(mas[i]){
				if(j-v[i]-v[mas[i]]>=0 && i>=2) ap[i][j]=max(ap[i][j],ap[i-2][j-v[i]-v[mas[i]]]+v[mas[i]]*p[mas[i]]+v[i]*p[i]);
			}else if(j-v[i]>=0){
				ap[i][j]=max(ap[i][j],ap[i-1][j-v[i]]+v[i]*p[i]);
			}
		}
	}

	cout << ap[m][n] <<endl;	
}