#include <fstream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>

using namespace std;

ifstream fin("budgetb.in");
ofstream fout("budgetb.out");

const int Maxn = 32000 + 100;
const int Maxm = 60 + 10;
vector<int> Tree[Maxm];
vector<int> Tree_Prime;
int Fun[Maxm][Maxn];
int Tree_Worth[Maxm];
int N, M, S, P;

class poi
{
public:
	int u, v;
}W[Maxm];

void Init()
{
	memset(Tree_Worth, 0, sizeof(Tree_Worth));
	memset(Fun, 0, sizeof(Fun));
	
	return ;
}
void Read()
{
	fin>>N>>M>>S;
	
	for(int i=1;i<=M;i++)
	{
		fin>>W[i].u>>W[i].v;
		fin>>P;
		
		W[i].v *= W[i].u;
		Tree[P].push_back(i);
	}
	return ;
}
void DFS(int Root)
{
	Tree_Worth[Root] = 1;
	for(int i=0;i<Tree[Root].size();i++)
	{
		Tree_Prime.push_back(Tree[Root][i]);
		DFS(Tree[Root][i]);
		Tree_Worth[Root] += Tree_Worth[Tree[Root][i]];
	}
	return ;
}
int main()
{
	Init();
	
	Read();
	
	DFS(0);
	
	for(int i=M-1;i>=0;i--)
	{
		int Now = Tree_Prime[i];
		for(int j=N;j>=W[Now].u;j--)
			Fun[i][j] = max(Fun[i+1][j-W[Now].u]+W[Now].v, Fun[i+Tree_Worth[Now]][j]);
		for(int j=W[Now-1].u;j>0;j--)
			Fun[i][j] = Fun[i+Tree_Worth[Now]][j];
	}
	
	fout<<Fun[0][N]<<endl;
	
	fin.close();
	fout.close();
	
	return 0;
}