//https://www.luogu.com.cn/problem/P1064
//P1064 [NOIP2006 提高组] 金明的预算方案
//author:Ice_Cold_Tea
//time:2022/7/21 11:33
#include<bits/stdc++.h>
#define rg register
#define il inline
#define ll long long
#define MAXN 32001
#define MAXM 61
using namespace std;
ll n,m,w[MAXM],v[MAXM],lson[MAXM],rson[MAXM],f[MAXM];
bool son[MAXM];
int main()
{
    cin>>n>>m;
    for (rg ll i=1;i<=m;++i)
    {
        cin>>w[i]>>v[i];v[i]*=w[i];//weight重量 value价值
        ll p;cin>>p;
        if (!p)
        {
            son[i]=1;
            if (lson[p]) rson[p]=i;
            else lson[p]=i;
        }
    }
    for (rg ll i=1;i<=m;++i)
    {
        if (son[i]) continue;//只考虑主件的情况
        for (rg ll j=n;j>=w[i];--j)
        {
            f[j]=max(f[j-w[i]]+v[i],f[j]);
            if (lson[i]&&j>=w[lson[i]]+w[i])//附件1
            {
                f[j]=max(f[j],f[j-w[lson[i]]-w[i]]+v[i]+v[lson[i]]);
            }
            if (rson[i]&&j>=w[rson[i]]+w[i])//附件2
            {
                f[j]=max(f[j],f[j-w[rson[i]]-w[i]]+v[i]+v[rson[i]]);
            }
            if (lson[i]&&rson[i]&&j>=w[lson[i]]+w[rson[i]]+w[i])//附件1和附件2
            {
                f[j]=max(f[j],f[j-w[lson[i]]-w[rson[i]]-w[i]]+v[i]+v[lson[i]]+v[rson[i]]);
            }
        }
    }
    cout<<f[n];
    return 0;
}