#include <bits/stdc++.h>
using namespace std;
vector<int> parent, rank2;
void make_set(int v) {
  parent[v] = v;
  rank2[v] = 0;
}
int find_set(int v) {
  if (v == parent[v]) return v;
  return parent[v] = find_set(parent[v]);
}
void union_sets(int a, int b) {
  a = find_set(a);
  b = find_set(b);
  if (a != b) {
    if (rank2[a] < rank2[b]) swap(a, b);
    parent[b] = a;
    if (rank2[a] == rank2[b]) rank2[a]++;
  }
}
struct Edge {
  int u, v, weight;
  bool operator<(const Edge& other) const {
    return this->weight < other.weight;
  }
};
vector<Edge> e2;
int vis[100010];
vector<int> adj[100010];
void dfs(int v) {
  if (vis[v]) return;
  vis[v] = 1;
  for (auto z : adj[v]) {
    dfs(z);
  }
}
int n;
bool connected() {
  for (int i = 1; i <= n; i++) {
    if (!vis[i]) return false;
  }
  return true;
}
int main() {
  int t;
  cin >> t;
  while (t--) {
    int m, k;
    cin >> n >> m >> k;
    vector<Edge> edges;
    e2.clear();
    for (int i = 0; i < m; i++) {
      Edge e;
      cin >> e.u >> e.v >> e.weight;
      int tmp = e.weight;
      if (e.weight < k)
        e.weight = 0;
      else
        e.weight -= k;
      edges.push_back(e);
      if (tmp <= k) {
        e.weight = tmp;
        e2.push_back(e);
      }
    }
    sort(edges.begin(), edges.end());
    map<Edge, int> mark;
    int min_weight;
    for (Edge z : edges) {
      if (z.weight == 0) continue;
      min_weight = min(min_weight, z.weight);
    }
    long long fans = 9223372036854775807LL;
    for (Edge ee : edges) {
      if (ee.weight == 0) continue;
      if (mark.count(ee) != 0) continue;
      int cost = 0;
      vector<Edge> result;
      parent.resize(n + 1);
      rank2.resize(n + 1);
      for (int i = 0; i < n; i++) make_set(i);
      result.push_back(ee);
      union_sets(ee.u, ee.v);
      mark[ee] = 1;
      for (Edge e : edges) {
        if (find_set(e.u) != find_set(e.v)) {
          mark[e] = 1;
          cost += e.weight;
          result.push_back(e);
          union_sets(e.u, e.v);
        }
      }
      long long ans = 0;
      for (Edge z : result) {
        ans += z.weight;
      }
      if (ans != 0)
        fans = min(fans, ans);
      else
        fans = min_weight;
    }
    memset(vis, 0, sizeof vis);
    long long ans2 = 9223372036854775807LL;
    for (auto z : e2) {
      adj[z.u].push_back(z.v);
      adj[z.v].push_back(z.u);
    }
    dfs(1);
    if (connected()) {
      for (Edge z : e2) {
        ans2 = min((long long)k - z.weight, ans2);
      }
    }
    cout << min(ans2, fans) << endl;
  }
}
