from sys import stdin,stdout
from math import gcd,sqrt,factorial,pi,inf
from collections import deque,defaultdict
from bisect import bisect,bisect_left
from time import time
from itertools import permutations as per
input=stdin.readline
R=lambda:map(int,input().split())
I=lambda:int(input())
S=lambda:input().rstrip('\r\n')
L=lambda:list(R())
P=lambda x:stdout.write(str(x)+'\n')
lcm=lambda x,y:(x*y)//gcd(x,y)
nCr=lambda x,y:(f[x]*inv((f[y]*f[x-y])%N))%N
inv=lambda x:pow(x,N-2,N)
sm=lambda x:(x**2+x)//2
N=10**9+7
def dsu(x):
p=x
while v[x]!=x:
x=v[x]
v[p]=x
return x
for _ in range(I()):
n,m,k=R()
x = 0
g=sorted([L() for i in range(m)],key=lambda x:x[-1])
v=[i for i in range(n+1)]
d=inf
ans=0
for a,b,s in g:
p=dsu(a)
q=dsu(b)
d=min(d,abs(s-k))
if p!=q:
v[p]=v[q]
ans+=max(0,s-k)
print(ans if ans else d)#pragma GCC optimize("03")
#include<bits/stdc++.h>
using namespace std;
#define T int t; cin>>t; while(t--)
#define ll long long
#define vec vector
#define all(x) x.begin(), x.end()
const double pi=3.14159265358979323846;
const int N=2e5+5, mod=1e9+7, inf=0x3f3f3f3f;
int dx[] = { 0, 0, 1, -1, 1, 1, -1, -1 };
int dy[] = { 1, -1, 0, 0, 1, -1, 1, -1 };
class dsu{
int parent[N], sz[N];
public:
dsu(int n){
for(int i=1; i<=n; i++) parent[i]=i, sz[i]=1;
}
int find_parent(int u){
if(parent[u]==u) return u;
return parent[u]= find_parent(parent[u]);
}
bool is_con(int u, int v){
return find_parent(u)== find_parent(v);
}
void con(int u, int v){
u= find_parent(u), v= find_parent(v);
if(is_con(u,v)) return;
if(sz[u]<sz[v]) swap(u, v);
parent[v]=u;
sz[u]+=sz[v];
}
};
int main(){
ios_base::sync_with_stdio(0), cout.tie(0), cin.tie(0);
T{
ll n, m, k; cin>>n>>m>>k;
dsu H(n);
ll sum=0, res=mod;
vec<pair<ll, pair<int, int>>>x;
for(int i=0; i<m; ++i){
int a, b, c; cin>>a>>b>>c;
res=min(res, abs(c-k));
x.push_back({max((ll)0, c-k),{a, b}});
}
sort(all(x));
for(auto it: x){
int a=it.second.first, b=it.second.second, c=it.first;
if(!c) H.con(a, b);
else{
if(!H.is_con(a, b)){
sum+=c;
H.con(a, b);
}
}
}
if(!sum)cout<<res<<'\n';
else cout<<sum<<'\n';
};
}1399A - Remove Smallest | 208A - Dubstep |
1581A - CQXYM Count Permutations | 337A - Puzzles |
495A - Digital Counter | 796A - Buying A House |
67A - Partial Teacher | 116A - Tram |
1472B - Fair Division | 1281C - Cut and Paste |
141A - Amusing Joke | 112A - Petya and Strings |
677A - Vanya and Fence | 1621A - Stable Arrangement of Rooks |
472A - Design Tutorial Learn from Math | 1368A - C+= |
450A - Jzzhu and Children | 546A - Soldier and Bananas |
32B - Borze | 1651B - Prove Him Wrong |
381A - Sereja and Dima | 41A - Translation |
1559A - Mocha and Math | 832A - Sasha and Sticks |
292B - Network Topology | 1339A - Filling Diamonds |
910A - The Way to Home | 617A - Elephant |
48A - Rock-paper-scissors | 294A - Shaass and Oskols |