#include <bits/stdc++.h>
using namespace std;
long long i,j,n,m,v[100],p[100],q[100],num[100],ans[50000];

int main(){
    cin>>n>>m;
    for(i=1;i<=m;i++){
        cin>>v[i]>>p[i]>>q[i];
        num[i]=v[i]*p[i];
    }
    for(i=1;i<=m;i++)
       if(q[i]!=0){
         v[q[i]]+=v[i];
         num[q[i]]+=num[i];
       }
    for(i=1;i<=m;i++)
       if(q[i]==0){
        for(j=n;j>=v[i];j--)
           ans[j]=max(ans[j],ans[j-v[i]]+num[i]);
       }
    cout<<ans[n]<<endl;
    return 0;
}