C++ :

#include<cstdio>
#include<cstring>
using namespace std;
int f[320010],v[70],w[70],q[70],N,m;
int main()
{
	memset(f,0,sizeof(f));
	int i,j;
	scanf("%d%d",&N,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&v[i],&w[i],&q[i]);
		w[i]=v[i]*w[i];
	}
	for(i=1;i<=m;i++)
	{
		if(q[i]>0)
		{
			v[i]=v[i]+v[q[i]];
			w[i]=w[i]+w[q[i]];
		}
	}
	for(i=1;i<=m;i++)
	{
		for(j=N;j>=v[i];j--)
		{
			if((j>=v[i]) && (f[j]<f[j-v[i]]+w[i]))f[j]=f[j-v[i]]+w[i];
		}
	}
	printf("%d",f[N]);
	return 0;
}