#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;
const int M = 500005;
const int N = 26000005;
#define pb push_back
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int T,n,m,k,ans,fa[M],a[M],b[M],f[N],h[N];
vector<int> g[M];
void solve(int *f,int A,int B)
{
	static int p[M]={},q[M]={};
	int h=1,t=0;
	for(int i=0,j=0;i<=m;i++,j+=B)
	{
		while(h<=t && p[t]<=f[i]-j) t--;
		p[++t]=f[i]-j;q[t]=i;
		while(h<=t && q[h]<i-A) h++;
		f[i]=p[h]+j;
	}
}
void dfs1(int u)
{
	if(a[u]) solve(f+u*k,a[u],b[u]);
	for(int v:g[u])
	{
		memcpy(f+v*k,f+u*k,T);
		dfs1(v);
		int *s=f+u*k+1,*e=f+v*k;
		for(int i=1;i<=m;i++,s++,e++)
			*s=max(*s,*e+b[v]);
	}
}
void dfs2(int u,int x)
{
	x+=b[u];
	for(int v:g[u])
	{
		memcpy(h+v*k,h+u*k,T);
		dfs2(v,x);
		int *s=h+u*k+1,*e=h+v*k;
		for(int i=1;i<=m;i++,s++,e++)
			*s=max(*s,*e+b[v]);
	}
	if(g[u].empty())
	{
		int *s=f+u*k+m,*e=h+u*k;
		for(int i=0;i<=m;i++,s--,e++)
			ans=max(ans,*s+*e+x);
	}
	if(a[u]) solve(h+u*k,a[u],b[u]);
}
void work()
{
	n=read();m=read();ans=0;
	k=m+1;T=k*sizeof(int);
	memset(f,0,sizeof f);
	memset(h,0,sizeof h);
	for(int i=1;i<=n;i++) g[i].clear();
	for(int i=1;i<=n;i++)
	{
		fa[i]=read();
		if(i>1) g[fa[i]].pb(i);
		a[i]=read()-1;b[i]=read();
	}
	dfs1(1);
	for(int i=1;i<=n;i++) g[i].clear();
	for(int i=n;i>1;i--) g[fa[i]].pb(i);
	dfs2(1,0);
	printf("%d\n",ans);
}
signed main()
{
	int Case=read();
	while(Case--) work();
}