#include <bits/stdc++.h>
using namespace std;
const int N = 2 * 1e5 + 1;
const int oo = 1e8;
int par[N];
int sum[N];
int to_save[N];
int res[N];
int x, y, z, l, r, mid, pos, posr, p = 0, minpos = oo, posi, posmin = 0, posk,
                                   maxres = 0;
pair<int, int> to_solve[N];
struct Node {
  int cto, ctt, dis;
} city[3 * N];
bool cmp(Node a, Node b) { return a.dis < b.dis; }
int find_set(int p) { return (par[p] == p) ? p : par[p] = find_set(par[p]); }
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n, m, k;
    cin >> n >> m >> k;
    pos = 0;
    p = 0;
    for (int i = 1; i <= n; i++) par[i] = i, sum[i] = 1;
    for (int i = 1; i <= m; i++)
      cin >> city[i].cto >> city[i].ctt >> city[i].dis;
    sort(city + 1, city + m + 1, cmp);
    l = 1, r = m;
    while (true) {
      mid = (l + r) / 2;
      if (l == mid || r == mid) break;
      if (city[mid].dis >= k)
        r = mid;
      else
        l = mid;
    }
    if (pos == 0) {
      for (int i = l; i <= r; i++)
        if (city[i].dis > k) {
          pos = i;
          break;
        } else
          posmin = i;
    }
    if (posmin != 0) minpos = k - city[posmin].dis;
    if (city[pos].dis - k <= k - city[posmin].dis && pos != 0) {
      x = find_set(city[pos].cto), y = find_set(city[pos].ctt);
      if (x != y) {
        par[y] = x;
        sum[x] += sum[y];
        if (sum[x] == n) {
          cout << city[pos].dis << endl;
          p = 1;
        }
      }
      minpos = city[pos].dis - k;
      pos++;
    }
    if (p == 0 && posmin != 0) {
      for (int i = 1; i <= posmin; i++) {
        x = find_set(city[i].cto), y = find_set(city[i].ctt);
        if (x == y) continue;
        par[y] = x;
        sum[x] += sum[y];
        if (sum[x] == n) {
          cout << minpos << endl;
          p = 1;
          break;
        }
      }
    }
    if (pos != 0 && p != 1)
      for (int i = pos; i <= m; i++) {
        x = find_set(city[i].cto), y = find_set(city[i].ctt);
        if (x == y) continue;
        par[y] = x;
        sum[x] += sum[y];
        maxres += city[i].dis - k;
        if (sum[x] == n) {
          cout << maxres << endl;
          p = 1;
          break;
        }
      }
  }
}
