#include <bits/stdc++.h>
using namespace std;
//debug
#ifdef grief
#define debug(...) do{\
	fprintf(stderr , "%s - %d : (%s) = " , __PRETTY_FUNCTION__ , __LINE__ , #__VA_ARGS__ );\
	_DO(__VA_ARGS__);\
}while(0)
template<typename I> 				void _DO(I&&x){	cerr<<x<<endl;	}
template<typename I,typename...T>	void _DO(I&&x,T&&...tail){	cerr<<x<<" , ";	_DO(tail...);	}
template<typename _a,typename _b> 	ostream& operator << (ostream &_s,const pair<_a,_b> &_p)
{	return _s<<'('<<_p.first<<','<<_p.second<<')';	}
#define IOS
#else
#define debug(...)
#define IOS do{ios_base::sync_with_stdio(0); cin.tie(0);}while(0);
#endif
//type
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,double> pp;
typedef priority_queue<pll,vector<pll>,greater<pll> > heap;
//macro
#define SZ(x) ((ll)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define stp setprecision(30)<<fixed
const ll INF=0x3f3f3f3f3f3f3f3f;
const int NF=0x3f3f3f3f;
const ll MAX=1e3+5,Mlg=__lg(MAX)+2;
const ll MOD=1e9+7;
const double eps=1e-7;
// ready~ go!
// let's coding and have fun!
// I can't solve this problem!
int n,k,C[MAX],L[MAX],dp[MAX][100005];
vector<int> son[MAX];
void dfs(int u,int sz){
	for(int i:son[u]){
		for(int j=0;j<=sz-C[i];j++)	dp[i][j]=dp[u][j];
		dfs(i,sz-C[i]);
		for(int j=C[i];j<=sz;j++)	dp[u][j]=max(dp[u][j],dp[i][j-C[i]]+L[i]);
	}
	return;
}
int main(){
	IOS
	int T;	cin>>T;
	while(T--){
		cin>>n>>k;
		for(int i=0;i<n;i++)	son[i].clear();
		for(int i=1;i<=n;i++){
			int p;
			cin>>p>>C[i]>>L[i];
			son[p].eb(i);
		}
		memset(dp[0],0,k*4+4);
		dfs(0,k);
		cout<<dp[0][k]<< '\n';
	}
	return 0;
}