#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll,ll> pairll;
typedef vector<ll> vll;

long long readInt()
{
    long long in; scanf("%lld", &in); return in;
}

long long absval(long long k)
{
    if(k >= 0) return k;
    return 0-k;
}

struct graph
{
  ll n,k;
  vector<vector<pairll>> g;
  vector<ll> dp,dp2;
 
  graph(ll n, ll k):n(n),k(k),g(n+1),dp(n+1),dp2(n+1){}
 
  void add_edge(int u, int v, ll c){
    g[u].push_back({v,c});
  }
 
  void dijkstra(int s){
    dp.assign(n+1, INT64_MAX);
    dp[s]=0;
    auto comp = [&](int i, int j){return dp[i]>dp[j];};
    priority_queue <ll, vector<ll>, decltype(comp)> pq(comp);
    pq.push(s);
    while (!pq.empty()){
      int u = pq.top(); pq.pop();
      for(int i=0; i<g[u].size(); i++){
        int v = g[u][i].first;
        ll d = g[u][i].second;
        if(dp[v] > min(dp[v],max(dp[u],d))){
          pq.push(v);
          dp[v] = min(dp[v],max(dp[u],d));
        }
      }
    }
  }
};

struct Edge {
    int to = -1,w = 1e9;
    bool operator<(Edge const& e)const{return make_pair(w, to) < make_pair(e.w, e.to);}
};

struct graph2
{
  int n;
  vector<vector<Edge>> g;

  graph2(int n):n(n),g(n){}

  void add_edge(int u, int v, int w){
    g[u].push_back({v,w});
    g[v].push_back({u,w});
  }
  
  //O(ElogV)
  vector<vector<Edge>> mst(){
    vector<vector<Edge>> res(n);
    vector<int> sel(n,0);
    vector<Edge> min_e(n);
    min_e[0].w=0;
    set<Edge>st;
    st.insert({0,0});
    for (int i = 0; i < n; ++i){
      if(st.empty()){
        res.clear();
        return res;
      }
      int v=st.begin()->to;
      sel[v]=1;
      st.erase(st.begin());
      if(min_e[v].to != -1){
        res[v].push_back({min_e[v].to, min_e[v].w});
      }
      for(Edge e: g[v]){
        if(!sel[e.to] and e.w<min_e[e.to].w){
          st.erase({e.to, min_e[e.to].w});
          min_e[e.to]={v,e.w};
          st.insert({e.to, e.w});
        }
      }
    }
    return res;
  }
  
  int mst_cost(){
    vector<vector<Edge>> res = mst();
    int tot = 0;
    for (int i = 0; i < n; ++i){
      for(auto p: res[i]){
        tot += p.w;
      }
    }
    return tot;
  }
};

int main()
{
    ll T = readInt();

    while(T--)
    {
        ll N = readInt(), M = readInt(), K = readInt();

        graph g(N,K);
        graph2 g2(N);

        ll pred = INT64_MAX, per = INT64_MAX;
        for(ll i = 0; i < M; i++)
        {
            ll u = readInt(), v = readInt(), c = readInt();

            g.add_edge(u,v,c);
            g.add_edge(v,u,c);
            g2.add_edge(u-1,v-1,max(0LL,c-K));

            if(pred > absval(K-c))
            {
                pred = absval(K-c);
                per = c;
            }
            else if(pred == absval(K-c))
            {
                per = max(per,c);
            }
        }

        g.dijkstra(1);

        ll ans = -1;
        for(ll i = 1; i <= N; i++)
        {
            ans = max(ans,g.dp[i]);
        }
        ll ans2 = ans;
        if(ans <= K)
        {
            if(absval(K-ans) > pred)
            {
                if(ans < per)
                {
                    ans = per;
                }
            }
            ans = absval(K - ans);
        }
        else
        {
            ans = g2.mst_cost();
        }

        
        
        printf("%lld\n", ans);
    }
}
/*
1
5 5 41
1 2 19
1 5 35
2 4 49
3 4 64
3 5 50
*/