#include<bits/stdc++.h>
#define rep(i,n) for(int i=1;i<=n;++i)
#define N 100005
using namespace std;
typedef long long ll;
int b[N],v[N<<1],c[N<<1],f[N<<1],tot;
int u[17][N],d[N],n,T,p,x,y,z;
ll ans[N],fins;
ll sqr(int x){return 1ll*x*x;}
void add(int x,int y,int z){v[++tot]=y,c[tot]=z,f[tot]=b[x],b[x]=tot;}
ll cal(int x,int y){return ans[y]+p+sqr(d[x]-d[y]);}
ll cp(int x){return ans[x]+sqr(d[x]);}
ll cross(int x,int y,int z){return (cp(z)-cp(x))*(d[y]-d[x])-(cp(y)-cp(x))*(d[z]-d[x]);}
int ss;
void dfs(int x,int fa){
	if(fa==0)ans[x]=0;else{
		ss=fa;
		for(int i=16;~i;--i)if(u[0][u[i][ss]]!=0&&cal(x,u[i][ss])>=cal(x,u[0][u[i][ss]]))ss=u[i][ss];
		//printf("%d %d %d\n",x,ss,u[0][ss]);
		ans[x]=cal(x,ss);
		if(u[0][ss]!=0)ans[x]=min(ans[x],cal(x,u[0][ss]));
	}
	ss=fa;
	for(int i=16;~i;--i)if(u[0][u[i][ss]]!=0&&cross(u[0][u[i][ss]],u[i][ss],x)<=0)ss=u[i][ss];
	if(u[0][ss]!=0&&cross(u[0][ss],ss,x)<=0)u[0][x]=u[0][ss];else u[0][x]=ss;
	//printf("fa:%d %d\n",x,u[0][x]);
	rep(i,16)u[i][x]=u[i-1][u[i-1][x]];
	for(int i=b[x];i;i=f[i])if(v[i]!=fa)
		d[v[i]]=d[x]+c[i],dfs(v[i],x);
}
int main(){
	for(scanf("%d",&T);T--;){
		scanf("%d%d",&n,&p);
		tot=0;rep(i,n){
			b[i]=0;
			for(int j=0;j<=16;++j)u[j][i]=0;
		}
		rep(i,n-1)scanf("%d%d%d",&x,&y,&z),add(x,y,z),add(y,x,z);
		dfs(1,0);
		//rep(i,n)printf("%lld\n",ans[i]-p);
		if(n==1){puts("0");continue;}
		fins=0;rep(i,n)fins=max(fins,ans[i]);
		printf("%lld\n",fins-p);
	}
	return 0;
}