#include <bits/stdc++.h>
using namespace std;
void solve() {
  long long n, m, k;
  cin >> n >> m >> k;
  vector<vector<pair<long long, long long>>> lst(n);
  vector<bool> used(n);
  {
    long long u, v, sl;
    for (int i = 0; i < m; ++i) {
      cin >> u >> v >> sl;
      --u;
      --v;
      lst[u].push_back({v, sl});
      lst[v].push_back({u, sl});
    }
  }
  priority_queue<pair<long long, pair<long long, long long>>> q;
  q.push({INT_MAX, {0, k}});
  long long ans = 0;
  long long v, s;
  long long i;
  long long mn = INT_MAX, vl = -1;
  long long mn2 = INT_MAX, vl2 = -1;
  long long mn3 = INT_MAX, vl3 = -1;
  long long t = n;
  while (t--) {
    if (!t) {
      while (!q.empty()) {
        if (used[q.top().second.first]) {
          q.pop();
          continue;
        }
        if (q.top().second.second > k) {
          if (mn > q.top().second.second - k) {
            mn = q.top().second.second - k;
            vl = q.top().second.second;
          }
        } else {
          if (mn2 > k - q.top().second.second) {
            mn2 = k - q.top().second.second;
            vl2 = q.top().second.second;
          }
        }
        q.pop();
      }
      if (mn == INT_MAX) {
        ans += k - max(vl2, vl3);
      } else {
        if (mn2 == INT_MAX) {
          ans += vl - k;
        } else {
          if (mn2 > mn3) {
            mn2 = mn3;
            vl2 = vl3;
          }
          if (mn > mn2) {
            ans += k - vl2;
          } else if (mn < mn2) {
            ans += vl - k;
          } else {
            ans += vl - k;
          }
        }
      }
    } else {
      while (used[q.top().second.first]) {
        q.pop();
      }
      ans += max((long long)0, q.top().second.second - k);
      used[q.top().second.first] = 1;
      v = q.top().second.first;
      s = q.top().second.second;
      q.pop();
      for (i = 0; i < lst[v].size(); ++i) {
        if (!used[lst[v][i].first]) {
          if (lst[v][i].second > k) {
            q.push({0 - (lst[v][i].second - k), lst[v][i]});
          } else {
            if (mn3 > k - lst[v][i].second) {
              mn3 = k - lst[v][i].second;
              vl3 = lst[v][i].second;
            }
            q.push({INT_MAX - (k - lst[v][i].second), lst[v][i]});
          }
        }
      }
    }
  }
  cout << ans;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int tt;
  cin >> tt;
  while (tt--) {
    solve();
    cout << "\n";
  }
}
