#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 3;
int n, m, k;
int F[N];
pair<int, pair<int, int> > kr[N];
vector<pair<int, pair<int, int> > > e;
int find(int v) {
  if (F[v] != v) {
    F[v] = find(F[v]);
  }
  return F[v];
}
void polacz(int u, int v) {
  u = find(u);
  v = find(v);
  F[u] = v;
}
int main() {
  ios_base::sync_with_stdio(0);
  cout.tie(0);
  cin.tie(0);
  int q;
  cin >> q;
  while (q--) {
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
      F[i] = i;
    }
    e.clear();
    long long naj = 1e18;
    for (int i = 1; i <= m; i++) {
      long long x = long long(kr[i].first);
      cin >> kr[i].second.first >> kr[i].second.second >> x;
      naj = min(naj, x);
      if (x >= k) {
        x -= k;
      } else {
        x = 0;
      }
      kr[i].first = x;
    }
    long long wynik = 0;
    sort(kr + 1, kr + 1 + m);
    for (int i = 1; i <= m; i++) {
      int u = kr[i].second.first;
      int v = kr[i].second.second;
      if (find(u) != find(v)) {
        polacz(u, v);
        wynik += long long(kr[i].first);
      }
    }
    if (wynik == 0) {
      wynik += naj;
    }
    cout << wynik << endl;
  }
  return 0;
}
