#include <bits/stdc++.h>
using namespace std;

#define int long long

int n, m, k, maxd, minu = INT_MAX, res = INT_MAX;

bool visit[200005];

unordered_map<int, unordered_map<int, int>> speed;

vector<int> e[200005];

pair<int, pair<int, int>> edge[200005];

void init(){
    maxd = INT_MIN, minu = INT_MAX, res = INT_MAX;
    speed.clear();
    for(int i = 1; i <= n; i++){
        e[i].clear();
        visit[i] = false;
    }
}

int dfs(int root){
    //cout << "r " << root << endl;
    int cnt = 0;
    visit[root] = true;
    for(int i = 0; i < e[root].size(); i++){
        int v = e[root][i];

        if(speed[root][v] <= k && !visit[v])
            cnt += dfs(v);

        if(speed[root][v] > k)
            minu = min(minu, speed[root][v]);

        if(speed[root][v] <= k)
            maxd = max(maxd, speed[root][v]);
    }
    return cnt + 1;
}

int parent[200005], sth[200005];

int find(int x){
    if(parent[x] == x)
        return x;
    return find(parent[x]);
}

void mst(){
    //cout << "lmao" << endl;
    res = 0;

    int cnt = 0;

    sort(edge, edge + m);

    for(int i = 1; i <= n; i++){
        parent[i] = i;
        sth[i] = 0;
    }

    for(int i = 0; i < m; i++){
        // for(int i = 1; i <= n; i++)
        //     cout << parent[i] << ' ';
        auto t = edge[i].second;
        //cout << "   size " << edge[i].first << ' ';
        int a = find(t.first), b = find(t.second);        
        if(!(a == b)){
           // cout << "ditm " << endl;
            res += edge[i].first;
            if(sth[a] == sth[b]) sth[a]++;
            if(sth[a] > sth[b]) parent[b] = a;
            else parent[a] = b;
            cnt++;
        }
        if(cnt == n - 1)
            break;
    }
}


void inp(){
    cin >> n >> m >> k;
    for(int i = 1; i <= m; i++){
        int x, y, s;
        cin >> x >> y >> s;
        speed[x][y] = s;
        speed[y][x] = s;
        e[x].push_back(y);
        e[y].push_back(x);
        edge[i - 1] = {s, {x, y}};
    }
}

void solve(){
    inp();

    bool f = false;

    for(int i = 1; i <= n; i++){
        if(!visit[i]){
            int t = dfs(i);
            //cout << "t: " << t << endl;
            if(t >= n){
                res = min(k - maxd, min(minu - k, res));
                f = true;
                break;
            }
           // cout << maxd << ' ' << minu << endl;
           
        }
    }
    if(!f){
        for(int i = 0; i < m; i++)
            edge[i].first = max(0ll, edge[i].first - k);

        mst();
    }
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    for(int i = 1; i <= t; i++){
        init();
        solve();
        cout << res << endl;
    }
}