#include <bits/stdc++.h>
using namespace std;
const int N=40010;
int p[110],w[110],n,m,f[110][N];
vector<int>v[N];
void dfs(int x,int fa){
    f[x][w[x]]=p[x];
    for(int i=0;i<v[x].size();i++){
        int u=v[x][i];
        if(u==fa)continue;
        dfs(u,x);
        for(int j=n;j>=w[x]+w[u];j--){
            for(int k=w[u];k<=j-w[x];k++){
                f[x][j]=max(f[x][j],f[u][k]+f[x][j-k]);
            }
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int k,x;
        cin>>w[i]>>k>>x;
        p[i]=w[i]*k;
        v[i].push_back(x);
        v[x].push_back(i);
    }
    dfs(0,0);
    cout<<f[0][n];
    return 0;
}