#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 2e5 + 9; struct node { int v, w, id; }; vector<node> G[N]; int n, m, L, a[N]; namespace sub1 { bool chk(ll x) { ll res = 0; for (int i = 1; i < n; i++) { res += max(0ll, x - a[i]); if (res > L) return 0; } return 1; } void Main() { ll lt = 1, rt = 4e9, mid; while (lt < rt) { mid = (lt + rt + 1) >> 1; if (chk(mid)) lt = mid; else rt = mid - 1; } printf("%lld\n", lt); } } vector<int> lp; stack<pair<int, int> > st; int vis[N], ok; void dfs(int u, int lst, int fa) { if (ok) return; if (vis[u]) { lp.push_back(lst); while (1) { int v = st.top().first, w = st.top().second; st.pop(); if (v == u) break; lp.push_back(w); } ok = 1; return; } st.push(make_pair(u, lst)); vis[u] = 1; for (auto e : G[u]) { int v = e.v, w = e.w, id = e.id; if (id == fa) continue; dfs(v, w, id); } if (!st.empty()) st.pop(); } multiset<int> _st; void slv() { scanf("%d%d%d", &n, &m, &L); if (m == n - 1) { for (int i = 1; i <= m; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); a[i] = w; } sub1::Main(); return; } for (int i = 1; i <= n; i++) { G[i].clear(); vis[i] = 0; } _st.clear(); for (int i = 1; i <= m; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); G[u].push_back({v, w, i}); G[v].push_back({u, w, i}); _st.insert(w); } lp.clear(), ok = 0; while (!st.empty()) st.pop(); dfs(1, 0, 0); for (int i : lp) _st.erase(_st.find(i)); int tp = 0; for (auto it = _st.begin(); it != _st.end(); it++) a[++tp] = *it; sort(lp.begin(), lp.end()); a[++tp] = lp[0] + lp[1]; for (int i = 2; i < lp.size(); i++) a[++tp] = lp[i]; sub1::Main(); } signed main() { int id, T; scanf("%d%d", &id, &T); while (T--) slv(); return 0; }