#include<iostream>
#include<string>
#include<algorithm>
#include<map>
#include<unordered_map>
#include<vector>
#include<set>
#include<queue>
#include<stack>
#include <math.h>
#include<climits>
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define deb(x) cout<<x<<"\n";
#define deB(x,y) cout<<x<<" "<<y<<"\n";
#define Deb(x,y,z) cout<<x<<" "<<y<<" "<<z<<"\n";
#define YES cout<<"YES\n";
#define Yes cout<<"Yes\n";
#define NO cout<<"NO\n";
#define No cout<<"No\n";
#define clt(x) 63-__builtin_clzll(x)
#define bct(x) __builtin_popcountll(x)
#define all(v) (v).begin(),(v).end()
#define pi pair<ll,ll>
#define vi vector<ll>
#define vpi vector<pair<ll,ll>>
#define maxq priority_queue<ll>
#define minq priority_queue<ll,vector<ll>, greater<ll>>
#define cont continue;
#define reto return 0;
#define sz size()
#define spmod 1116295198451
#define mod 1000000007
#define md 998244353 
#define N 200009
#define int ll
#define LG 20
//typedef tree<int,null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> //pbds;
ll rnk[N],parent[N],ans[N];
ll par[LG][N],level[N],tot[N],ht[LG][N];
ll c[N];
ll n;
vpi a[N];
void make_set(int v) {
    parent[v] = v;
    rnk[v] = 0;
}
int find_set(int v) {
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}
 
void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (rnk[a] < rnk[b])
            swap(a, b);
        parent[b] = a;
        if (rnk[a] == rnk[b])
            rnk[a]++;
    }
}
struct Edge {
    int u, v, w,in;
    ll f=0;
    bool operator<(Edge const& other) {
        return w < other.w;
    }
};
void dfs(ll k,ll parent,ll d)
{
  par[0][k]=parent;
  level[k]=d;
  tot[k]=1;
  for(auto it:a[k])
  {
    if(it.ff==parent)
      continue;
  	ht[0][it.ff]=it.ss;
    dfs(it.ff,k,d+1);
    tot[k]+=tot[it.ff];
  }
}
void precompute()
{
  for(ll i=1;i<LG;i++)
  {
    for(ll j=1;j<=n;j++)
    {
      if(par[i-1][j])
          par[i][j]=par[i-1][par[i-1][j]];
      ht[i][j]=max(ht[i-1][j],ht[i-1][par[i-1][j]]);
    }
  }
}
ll lca(ll u, ll v)
{
  if(level[u]<level[v])
      swap(u,v);
  ll diff=level[u]-level[v];
  for(ll i=LG-1;i>=0;i--)
  {
    if((1ll<<i) & diff)
    {
      u=par[i][u];
    }
  }
  if(u==v)
    return u;
  for(ll i=LG-1;i>=0;i--)
  {
    if(par[i][u] && par[i][u]!=par[i][v])
    {
      u=par[i][u];
      v=par[i][v];
    }
  }
  return par[0][u];
}
ll mxdis(ll node,ll d)
{
	ll i=LG-1,mx=0;
	while(i>-1)
	{
		if((1ll<<i)<=d)
			{
				mx=max(mx,ht[i][node]);
				node=par[i][node];
				d-=(1ll<<i);
			}
		i--;
	}
	return mx;
}

void solve()
{
	ll n,m,k,i,cost,ans=INT_MAX;
	cin>>n>>m>>k;
	i=1;
    while(i<=n)
    {
  		make_set(i);
  		a[i].clear();
  		i++;
  	}
	i=0;
	vector<Edge> E(m),e(m),result;
	while(i<m)
	{
		cin>>e[i].u>>e[i].v>>e[i].w;
		E[i].u=e[i].u;
		E[i].v=E[i].v;
		E[i].w=max(0ll,e[i].w-k);
		i++;
	}
	sort(all(E));
	ll u,v,l,mx;
	cost=0;
 	for (Edge &x : E) 
 	{
    	if (find_set(x.u) != find_set(x.v)) 
    	{
        	cost += x.w;
        	result.push_back(x);
        	union_sets(x.u, x.v);
        	x.f=1;
    	}
	}
	for(auto x:result)
		{
			//ans[x.in]=cost;
			a[x.u].pb({x.v,x.w});
			a[x.v].pb({x.u,x.w});
		}
	dfs(1,0,0);
	precompute();
	for(auto x:e)
	{
		if(x.f)
			cont;
		u=x.u;
		v=x.v;
		l=lca(u,v);
		//Deb(u,v,l)
		mx=max(mxdis(u,-level[l]+level[u]),mxdis(v,-level[l]+level[v]));
		//deb(mx)
		ans=min(ans,cost-mx+abs(k-x.w));
	}
	deb(ans)
}
int32_t main()
{
  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  #ifndef ONLINE_JUDGE
  	freopen("input.txt", "r", stdin);
  	freopen("output.txt", "w", stdout);
  #endif
  ll t=1;
  cin>>t;
  while(t--)
  {
  	solve();  
  }
}