#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define N 100001

typedef long long LL;

int P;

int front[N],to[N<<],nxt[N<<],val[N<<],tot;

int dis[N];

int head,tail,q[N];

LL dp[N];

void read(int &x)

{

    x=; char c=getchar();

    while(!isdigit(c)) c=getchar();

    while(isdigit(c)) { x=x*+c-''; c=getchar(); }

}

void add(int u,int v,int w)

{

    to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; val[tot]=w;

    to[++tot]=u; nxt[tot]=front[v]; front[v]=tot; val[tot]=w;

}

inline double X(int i,int j) { return dis[j]-dis[i]; }

inline double Y(int i,int j) { return 1LL*dis[j]*dis[j]+dp[j]-1LL*dis[i]*dis[i]-dp[i]; }

void dfs(int x,int y)

{

    int now_h=head,now_t=tail;

    int l=head,r=tail-,mid,tmp=-;

    while(l<=r)

    {

        mid=l+r>>;

        if(Y(q[mid],q[mid+])>=*dis[x]*X(q[mid],q[mid+])) tmp=mid,r=mid-;

        else l=mid+;

    }

    if(tmp!=-) head=tmp;

    else head=tail-;

    int j=q[head];

    dp[x]=1LL*(dis[x]-dis[j])*(dis[x]-dis[j])+P+dp[j];

    l=head,r=tail-,tmp=-;

    while(l<=r)

    {

        mid=l+r>>;

        if(Y(q[mid],q[mid+])*X(q[mid+],x)<=Y(q[mid+],x)*X(q[mid],q[mid+])) tmp=mid,l=mid+;

        else r=mid-;

    }

    if(tmp!=-) tail=tmp+;

    else tail=head+;

    int rr=q[tail];

    q[tail++]=x;

    for(int i=front[x];i;i=nxt[i])

        if(to[i]!=y)

        {

            dis[to[i]]=dis[x]+val[i];

            dfs(to[i],x);

        }

    head=now_h; q[tail-]=rr; tail=now_t;

}

void clear()

{

    tot=;

    memset(front,,sizeof(front));

}

int main()

{

    int T;

    read(T);

    int n,u,v,w;

    while(T--)

    {

        clear();

        read(n); read(P);

        for(int i=;i<n;++i)

        {

            read(u); read(v); read(w);

            add(u,v,w);

        }

        dp[]=-P;

        for(int i=front[];i;i=nxt[i])

        {

            head=; tail=;

            q[]=;

            dis[to[i]]=val[i];

            dfs(to[i],);

        }

        LL ans=;

        for(int i=;i<=n;++i) ans=max(ans,dp[i]);

        cout<<ans<<'\n';

    }

}