#include <iostream>
#include <math.h>
#include <string.h>
#include <stack>
#include <queue>
using namespace std;


struct item{
	int weight,value,father;
	queue<int> son;
};


int main(){
	int n,m;
	cin>>n>>m;
	stack<int> sta;
	item a[m+1];
	int dp[m+1][n+1];
	memset(dp,0,sizeof(dp));
	a[0].value = 0;
	a[0].weight = 0;
	for(int i=1;i<=m;i++){
		int w,v,f;
		cin>>w>>v>>f;
		a[i].weight = w;
		a[i].value = v*w;
		a[i].father = f;
		a[f].son.push(i);
	}
	sta.push(0);
//	int i=0;
	while(!sta.empty()){
//		i++;
//		cout<<i<<endl;
		if(!a[sta.top()].son.empty()){
			int index;
			sta.push(a[index=sta.top()].son.front());
			a[index].son.pop();
			continue;
		}
		int now=sta.top();
		if(now == 0)
			break;
		for(int i=n-a[now].weight;i>=0;i--){
			for(int j=0;j<=i;j++)
				dp[a[now].father][i+a[now].weight] = max(dp[a[now].father][i+a[now].weight],dp[a[now].father][i-j]+dp[now][j]+a[now].value);
		}
		sta.pop();
	}
//	for(int i=0;i<=m;i++){
//		for(int j=0;j<=n;j++)
//			cout<<dp[i][j]<<" ";
//		cout<<endl<<endl;
//	}
	cout<<dp[0][n];
	return 0;
}


/*
10 5
3 5 0
4 2 0
3 5 2
3 4 2
6 4 0
*/