#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vii;
typedef vector<vi> vvi;
typedef vector<pll> vll;
typedef vector<vl> vvl;

#define fori(i, n) for (int i = 0; i < n; i++)
#define ford(i, n) for (int i = n - 1; i >= 0; i--)
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define repd(i, a, b) for (int i = a; i >= b; i--)
#define trav(x, a) for (auto &x : a)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define endl '\n'
#define sz(a) (int)(a).size()
#define fi first
#define se second

clock_t time_p = clock();
void time_taken()
{
    time_p = clock() - time_p;
    cerr << "Time Taken : " << (float)(time_p) / CLOCKS_PER_SEC << "\n";
}

const ll mod = 1e9 + 7;
const ll INF = 1e18;

struct DSU
{
    vector<int> par;
    void init(int n)
    {
        par = vector<int>(n, -1);
    }
    int find(int x)
    {
        return par[x] < 0 ? x : par[x] = find(par[x]);
    }
    int size(int x)
    {
        return -par[find(x)];
    }
    bool merge(int x, int y)
    {
        x = find(x), y = find(y);
        if (x == y)
            return 0;
        if (par[x] > par[y])
            swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return 1;
    }
};

struct edge
{
    int u, v, w;
};

void solve()
{
    int n, m, k;
    cin >> n >> m >> k;
    vector<edge> es;
    vector<edge> e_tot;
    fori(_, m)
    {
        int u, v, w;
        cin >> u >> v >> w;
        --u, --v;
        if(w <= k)
            es.pb({u, v, w});
        
        if(w <= k)
            w = 0;
        else
            w = w - k;
        e_tot.pb({u, v, w});
    }
    ll ans = INF;

    {
        DSU uf;
        uf.init(n);
        int mx = 0,comps = n;
        for (auto [u, v, w] : es)
        {
            mx = max(mx, w);
            comps -= uf.merge(u, v);
        }
        if(comps==1){
            ans = min<ll>(ans, k - mx);
        }
    }
    {
        DSU uf;
        uf.init(n);

        sort(all(e_tot), [&](edge u, edge v) { return u.w < v.w; });

        ll cost = 0;
        for (auto [u, v, w] : e_tot)
        {
            if(uf.merge(u,v))
                cost += w;
        }

        // cerr << cost << endl;

        if(cost != 0){
            ans = min(ans, cost);
        }
        else{
            for(auto [u,v,w] : e_tot){
                if(w)
                    ans = min<ll>(ans, w);
            }
        }
    }
    cout << ans << endl;
}

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }

    time_taken();
    return 0;
}