自闭了，*1800 都不会了。。
先连所有边权不大于 \(k\) 的边，若图能连通，直接找一条边权与 \(k\) 最接近的改一下就好了。
否则跑一遍 Kruskal。
具体细节看代码。
Code：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200005, inf = 0x3f3f3f3f;
int T;
int n, m, k;
ll ans;
struct node {
int u, v, w;
node (){}
node (int _u, int _v, int _w) {
u = _u, v = _v, w = _w;
}
bool operator < (const node &x) const {
return w < x.w;
}
} E[N];
int fa[N];
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
bool merge(int x, int y) { x = find(x), y = find(y); if (x == y) return false; fa[x] = y; return true; }
void init() { for (int i = 1; i <= n; ++i) fa[i] = i; }
void solve() {
scanf("%d%d%d", &n, &m, &k);
for (int i = 1, u, v, w; i <= m; ++i) scanf("%d%d%d", &u, &v, &w), E[i] = node(u, v, w);
sort(E + 1, E + m + 1);
init();
for (int i = 1; i <= m; ++i) {
if (E[i].w > k) break;
merge(E[i].u, E[i].v);
}
int tot = 0;
for (int i = 1; i <= n; ++i) if (fa[i] == i) ++tot;
if (tot == 1) {
int mn = inf;
for (int i = 1; i <= m; ++i) mn = min(mn, abs(E[i].w - k));
return printf("%d\n", mn), void();
}
init();
ans = 0;
for (int i = 1; i <= m; ++i)
if (merge(E[i].u, E[i].v)) ans += max(0, E[i].w - k);
printf("%lld\n", ans);
}
int main() {
scanf("%d", &T);
while (T--) solve();
return 0;
}