#include <algorithm> #include <cstdio> #include <iostream> #include <tuple> #include <unordered_map> #include <vector> using namespace std; using i64 = long long; using Graph = unordered_map<int, vector<tuple<int, i64, int>>>; // u: (v, d) constexpr int N = 2e5; struct Solution { Graph G; vector<pair<int, int>> tree, cycle; bool vis[N + 5]; bool dfs(int u, int lst_id = -1) { bool res = false; vis[u] = true; for (auto [v, w, id] : G[u]) { if (id == lst_id) continue; if (vis[v] || dfs(v, id)) { cycle.emplace_back(w, id); res = true; } else tree.emplace_back(w, id); } return res; } bool check(i64 ans, int lim) { i64 need = 0; if (cycle.size() == 1) need += max(0LL, ans - cycle[0].first); else if (cycle.size() >= 2) { int n = cycle.size(); need += max(0LL, ans - cycle[0].first - cycle[1].first); for (int i = 2; i < n; ++i) need += max(0LL, ans - cycle[i].first); } for (auto [w, _] : tree) need += max(0LL, ans - w); return need <= lim; } inline bool eq(const tuple<int, int, int>& lhs, const tuple<int, int, int>& rhs) { return get<0>(lhs) == get<0>(rhs); } void solve() { int n, m, lim; cin >> n >> m >> lim; for (int i = 0; i < m; ++i) { int u, v, d; cin >> u >> v >> d; G[u].emplace_back(v, d, i); G[v].emplace_back(u, d, i); } for (int i = 1; i <= n; ++i) { int k = G[i].size(); sort(G[i].begin(), G[i].end()); for (int j = 1; j < k; ++j) { if (eq(G[i][j], G[i][j - 1])) { get<1>(G[i][j]) += get<1>(G[i][j - 1]); G[i].erase(G[i].begin() + j - 1); break; } } } i64 l = 0, r = 3e9; dfs(1); sort(cycle.begin(), cycle.end()); cycle.erase(unique(cycle.begin(), cycle.end()), cycle.end()); while (l < r) { i64 mid = (l + r + 1) >> 1; if (check(mid, lim)) l = mid; else r = mid - 1; } cout << l << '\n'; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); int t; cin >> t >> t; for (int i = 1; i <= t; ++i) Solution().solve(); return 0; }