#include <bits/stdc++.h>
using namespace std;
int dp[32001],n,m,v[61],p[61],q[61];
int main()
{
    //freopen("budget.in","r",stdin);
    //freopen("budget.out","w",stdout);
    cin>>m>>n;
    for(int i=1;i<=n;i++) cin>>v[i]>>p[i]>>q[i];
    for(int i=1;i<=n;i++)
    {
        int t;  //价格
        if(!q[i]) t=v[i];
        else t=v[i]+v[q[i]];
  
        int x;  //价值
        if(!q[i]) x=v[i]*p[i];
        else x=v[i]*p[i]+v[q[i]]*p[q[i]];
       
        for(int j=m;j>=t;j--)
        {
            dp[j]=max(dp[j],dp[j-t]+x);
        }
    }
    cout<<dp[m];
    return 0;
}