#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 0x3f3f3f3f;
struct edge {
  int u, v, dis;
  friend bool operator<(edge a, edge b) { return a.dis < b.dis; }
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int _;
  cin >> _;
  while (_--) {
    int n, m, k;
    cin >> n >> m >> k;
    vector<edge> g1, g2;
    for (int i = int(1); i <= int(m); i++) {
      int u, v, dis;
      cin >> u >> v >> dis;
      dis -= k;
      if (dis < 0)
        g1.push_back({u, v, dis});
      else
        g2.push_back({u, v, dis});
    }
    vector<int> fa(n + 1);
    int cnt = n;
    for (int i = int(1); i <= int(n); i++) fa[i] = i;
    function<int(int)> Find = [&](int x) {
      if (x == fa[x])
        return x;
      else
        return fa[x] = Find(fa[x]);
    };
    auto Union = [&](int a, int b) { fa[Find(b)] = Find(a); };
    sort(g1.begin(), g1.end());
    sort(g2.begin(), g2.end());
    int ans = inf;
    for (auto x : g1) {
      if (Find(x.u) != Find(x.v)) {
        cnt--;
        Union(x.u, x.v);
      }
      if (cnt == 1) {
        ans = min(ans, -x.dis);
      }
    }
    ll now = 0;
    bool f = false;
    for (auto x : g2) {
      if (Find(x.u) != Find(x.v)) {
        cnt--;
        Union(x.u, x.v);
      }
      f = true;
      now += x.dis;
      if (cnt == 1) {
        break;
      }
    }
    if (f)
      now = min(now, 1ll * ans);
    else
      now = ans;
    cout << now << '\n';
  }
  return 0;
}
