#include <bits/stdc++.h>
using namespace std;
long long n, t, m, k, e, u, c, d[200005], ans, second, n1, ans1;
map<pair<long long, long long>, long long> mp;
vector<int> v[200005];
priority_queue<pair<long long, pair<long long, long long> > > pq;
bool b[200005];
void solve(long long a) {
  d[a] = 0;
  ans = 0;
  while (pq.size() || a == 1) {
    b[a] = true;
    for (int i = 0; i < v[a].size(); i++) {
      long long b1 = mp[{v[a][i], a}];
      if (b[v[a][i]] == false && d[v[a][i]] > b1) {
        d[v[a][i]] = b1;
        pq.push({-d[v[a][i]], {v[a][i], a}});
      }
    }
    while (pq.size() && (b[pq.top().second.first] == true ||
                         -pq.top().first != d[pq.top().second.first])) {
      pq.pop();
    }
    if (pq.size() == 0) break;
    cout << a << " " << pq.top().second.second << " " << pq.top().second.first
         << endl;
    ans += mp[{pq.top().second.second, pq.top().second.first}];
    a = pq.top().second.first;
  }
}
int main() {
  cin >> t;
  while (t--) {
    mp.clear();
    for (int i = 1; i <= n; i++) {
      v[i].clear();
      b[i] = false;
    }
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
      d[i] = 1e18;
    }
    ans1 = 1e18;
    for (int i = 1; i <= m; i++) {
      cin >> e >> u >> second;
      ans1 = min(ans1, abs(k - second));
      mp[{e, u}] = max((long long)0, second - k);
      mp[{u, e}] = max((long long)0, second - k);
      v[e].push_back(u);
      v[u].push_back(e);
    }
    solve(1);
    if (ans == 0)
      cout << ans1 << endl;
    else
      cout << ans << endl;
  }
}
