#include <bits/stdc++.h>
using namespace std;
int const MAXN = 2e6 + 9;
vector<pair<int, int>> g[MAXN];
struct LCA {
  int timer;
  int l;
  vector<int> tin, tout;
  vector<vector<int>> up, maxi;
  vector<long long> dist, dep;
  LCA(int root, int n) {
    tin.resize(n + 1);
    tout.resize(n + 1);
    timer = 0;
    l = ceil(log2(n + 1));
    dist.assign(n + 1, 0);
    dep.assign(n + 1, 0);
    up.assign(n + 1, vector<int>(l + 1));
    maxi.assign(n + 1, vector<int>(l + 1));
    dfs(root, root, 0);
  }
  void dfs(int v, int p, int w) {
    tin[v] = ++timer;
    up[v][0] = p;
    maxi[v][0] = w;
    for (int i = 1; i <= l; ++i) {
      up[v][i] = up[up[v][i - 1]][i - 1];
      maxi[v][i] = max(maxi[v][i - 1], maxi[up[v][i - 1]][i - 1]);
    }
    for (auto cur : g[v]) {
      int u = cur.first;
      int w = cur.second;
      if (u == p) continue;
      dep[u] = dep[v] + 1;
      dist[u] = dist[v] + w;
      dfs(u, v, w);
    }
    tout[v] = ++timer;
  }
  bool is_ancestor(int u, int v) {
    return tin[u] <= tin[v] && tout[v] <= tout[u];
  }
  int lca(int u, int v) {
    if (is_ancestor(u, v)) return u;
    if (is_ancestor(v, u)) return v;
    for (int i = l; i >= 0; i--) {
      if (!is_ancestor(up[u][i], v)) u = up[u][i];
    }
    return up[u][0];
  }
  long long get_dist(int u, int v) {
    return dist[u] + dist[v] - 2 * dist[lca(u, v)];
  }
  long long get_best(int v, int d) {
    int ret = 0;
    for (int i = l; i >= 0; --i) {
      if (d & (1 << i)) {
        ret = max(ret, maxi[v][i]);
        v = up[v][i];
      }
    }
    return ret;
  }
};
struct DSU {
  vector<int> root, size;
  int cc;
  DSU(int n) {
    root.resize(n + 1);
    size.resize(n + 1);
    for (int i = 0; i <= n; i++) {
      root[i] = i;
      size[i] = 1;
    }
    cc = n;
  }
  int find_set(int x) {
    if (root[x] == x) return x;
    return root[x] = find_set(root[x]);
  }
  bool union_set(int u, int v) {
    u = find_set(u);
    v = find_set(v);
    if (u == v) return false;
    if (size[u] < size[v]) swap(u, v);
    root[v] = u;
    size[u] += size[v];
    cc--;
    return true;
  }
};
vector<pair<int, pair<int, int>>> edges;
map<pair<int, int>, int> mp;
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  int T;
  cin >> T;
  while (T--) {
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 1; i <= n + 9; i++) g[i].clear();
    edges.clear();
    mp.clear();
    DSU dsu(n);
    for (int i = 0; i < m; i++) {
      int u, v, w;
      cin >> u >> v >> w;
      mp[minmax(u, v)] = w;
      if (w <= k)
        w = 0;
      else
        w -= k;
      edges.push_back({w, minmax(u, v)});
    }
    sort(edges.begin(), edges.end());
    long long mst = 0;
    for (auto cur : edges) {
      long long w = cur.first;
      int u = cur.second.first;
      int v = cur.second.second;
      if (dsu.union_set(u, v)) {
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
        mst += w;
      }
    }
    LCA lca(1, n);
    long long ans = 1e18;
    for (auto e : edges) {
      int w = mp[e.second];
      int u = e.second.first;
      int v = e.second.second;
      int p = lca.lca(u, v);
      int d1 = lca.dep[p] - lca.dep[u];
      int d2 = lca.dep[p] - lca.dep[v];
      int mx = max(lca.get_best(u, d1), lca.get_best(v, d2));
      ans = min(ans, mst - mx + abs(w - k));
    }
    cout << ans << '\n';
  }
}
