#include<bits/stdc++.h>
#define ll long long 
using namespace std;
ll n,m;
ll value[61];
ll w[61];
ll a[61][61],x;
ll dp[61][32009];
inline ll read(){
	ll a=0;int f=0;char p=getchar();
	while(!isdigit(p)){f|=p=='-';p=getchar();}
	while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=getchar();}
	return f?-a:a;
}
void dfs(int id){
    for(int i=value[id];i<=n;i++) dp[id][i]=value[id]*w[id];
    for(int i=1;i<=a[id][0];i++){
        ll s=a[id][i];
        dfs(s);
        for(int j=n;j>=value[id];j--){
            for(int k=1;k<=j-value[id];k++){
                dp[id][j]=max(dp[id][j],dp[s][k]+dp[id][j-k]);
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);
    n=read();
    m=read();
    for(int i=1;i<=m;i++){
        value[i]=read();
        w[i]=read();
        x=read();
        a[x][0]++;
        a[x][a[x][0]]=i;
    }
    dfs(0);
    cout<<dp[0][n];
    return 0;
}