#include <bits/stdc++.h> using namespace std; #define ll long long #define int long long const int N = 2e5 + 5, M = 4e5 + 5; int CASE, T; int n, m, L, d[N], id[M]; int head[N], pos; struct Edge { int u, v, w, nxt; } e[M]; bool vis[N], mark[M]; int lp[N], nlp[N], pos1, pos2; inline int read() { int x = 0; char c = getchar(); while (c < '0' || c > '9') c = getchar(); x = x * 10 + c - '0'; c = getchar(); while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } return x; } inline void addEdge(int u, int v, int w) { e[++pos] = {u, v, w, head[u]}; head[u] = pos; } void init() { for (int i = 1; i <= n; i++) head[i] = vis[i] = mark[i] = id[i] = 0; for (int i = n + 1; i <= n + n; i++) mark[i] = id[i] = 0; pos = pos1 = pos2 = 0; } inline bool equal_edge(int i, int j) { return (i + 1) / 2 == (j + 1) / 2; } int dfs(int u, int fa) { if (vis[u]) return u; vis[u] = true; for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].v; if (v == fa && equal_edge(id[u], i)) continue; id[v] = i; int x = dfs(v, u); if (x) { lp[++pos1] = e[i].w; mark[i] = true; return (u == x ? 0 : x); } } return 0; } inline bool check(ll mid) { ll res1 = 0; for (int i = 1; i <= pos2; i++) if (nlp[i] < mid) res1 += mid - nlp[i]; if (res1 > L) return false; if (pos1 == 0) return true; ll res2 = 0, sum = 0, res3 = 0x3f3f3f3f3f3f3f3f; int mnw = 0x3f3f3f3f, mxw = 0; for (int i = 1; i <= pos1; i++) { if (lp[i] < mid) res2 += mid - lp[i]; mnw = min(mnw, lp[i]), mxw = max(mxw, lp[i]); } // cout << res2 << endl; if (mnw < mid) res2 -= mid - mnw; sum = res3 = res2; //cout << "........." << sum << endl; for (int i = 1; i <= pos1; i++) { if (mnw == lp[i]) continue; if (lp[i] + mnw < mid) res3 = min(res3, sum + (mid - mnw - lp[i]) - (lp[i] < mid ? mid - lp[i] : 0)); else res3 = min(res3, sum - (lp[i] < mid ? mid - lp[i] : 0)); } // cout << res1 << ' ' << res2 << ' ' << res3 << endl; return res1 + min(res2, res3) <= L; } void solve() { n = read(); m = read(); L = read(); init(); int u, v, w; for (int i = 1; i <= m; i++) { u = read(), v = read(), w = read(); addEdge(u, v, w), addEdge(v, u, w); } id[1] = 0; dfs(1, 0); for (int i = 1; i <= pos; i += 2) if (!mark[i] && !mark[i + 1]) nlp[++pos2] = e[i].w; // cout << pos1 << endl; // for (int i = 1; i <= pos1; i++) // printf("%d%c", lp[i], " \n"[i == pos1]); // cout << pos2 << endl; // cout << cnt << endl; // for (int i = 1; i <= pos2; i++) // printf("%d%c", nlp[i], " \n"[i == pos2]); // cout << check(80771707) << endl << endl;; // return; ll l = 0, r = 4e9 + 5, ans = 0; while (l <= r) { ll mid = (l + r) >> 1; if (check(mid)) { ans = mid; l = mid + 1; } else r = mid - 1; } printf("%lld\n", ans); } signed main() { CASE = read(); T = read(); while (T--) solve(); return 0; }