//看的题解的思路，大概就是说，先把同属于一个组里的东西先进行01背包，然后得到从主件花费到n的这么一个数组，然后再把这个数组往总的dp数组里放

#include<bits/stdc++.h>
using namespace std;
int n, m;
struct node
{
	int v;
	int w;
};
vector<node>h[65];
int dp[32005],f[32005], ff[32005];

int main()
{

	int v,p,q;
	node x;
	scanf("%d%d",&n,&m);
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=m;i++)
	{
	    scanf("%d%d%d",&v,&p,&q);
	    x.v=v;
	    x.w=v*p;
	    if(q==0) h[i].push_back(x);//主件就入自己的队
	    else h[q].push_back(x);//附件就入主件的队
	}
	for(int i=1;i<=m;i++)
	{
	    if(h[i].size()==0) continue;//如果不存在以i为主件的数组，continue
	    int vv=h[i][0].v;//0号是主件，vv是主件的体积（本题中为价钱）
	    int ww = h[i][0].w;//主件的重要性
	    int num=h[i].size()-1;//附件的数量
        ///cout<<vv<<" "<<ww<<" "<<num<<endl;//应该是没问题
	    //h[i][j]表示以i为主件的物品的所有附近，其中h[i][0]就是主件自己
	    //我要先对每个附件组进行dp，然后得出从0到V-c[i]的所有对应的值，即f'[0..V-c[i]]
	    //要先对除了主件以外的附件进行01背包，否则主件的体积会被算好几遍，然后最后都要加上主件的价值和重要度，
	    
	    memset(f, 0, sizeof(f));
	    memset(ff, 0, sizeof(ff));
	    for(int j = 1; j<=num; j++)//对所有的附件进行01背包
	        for(int k = n-vv; k>=h[i][j].v;k--){
	            f[k] = max(f[k], f[k-h[i][j].v]+h[i][j].w);
                ///cout<<f[k];
	            
	        }
	   
	    //加上主件的价格和价值
	    for(int j = 0; j<=n-vv; j++){//ff[0]就是只买主件
	        ff[j+vv] = f[j]+ww;//游标就是他的花费，函数值就是他的重要度
	        ///cout<<ff[j+vv];
	    }
	    ///cout<<ff[1199]<<" ";应该也没问题
        
           
	    //再放进到真正的背包里
	    //小于vv的就相当于啥也没放
	    //一共有从vv到n个物品
	    for(int k = n; k>=vv; k--)//这里还是有分组背包的感觉，就是ff中的这些数是互相冲突的，只能放一个，所以外层for先写容量
	        for(int j = vv; j<=n; j++)//依赖背包就是把附件主件这些，转化成了m-vv+1个物品(加的那个1就是只买主件的情况)
	            if(k>=j)dp[k] = max(dp[k], dp[k-j]+ff[j]);
	       
	   //cout<<dp[n]<<endl;
	            
	   
	   
	}
	printf("%d",dp[n]);
	return 0;
}