#include <bits/stdc++.h> #define int long long #define pii pair<int,int> #define push_back emplace_back #define mkp make_pair #define fir first #define sec second using namespace std; int n, m, l; vector <pii> ed[200005]; struct node { int val; bool b; } a[200005]; inline bool cmp(node x, node y) { if (x.val == y.val) return x.b < y.b; return x.val < y.val; } bool vis[200005]; pii st[200005]; int top; map <pii, bool> mp; bool ret; inline void dfs(int u, int fa) { // printf("%lld fa:%lld\n", u, fa); if (vis[u]) { while (st[top].fir != u) { mp[mkp(st[top].fir, st[top].sec)] = 1; mp[mkp(st[top].sec, st[top].fir)] = 1; top--; } mp[mkp(st[top].fir, st[top].sec)] = 1; mp[mkp(st[top].sec, st[top].fir)] = 1; ret = 1; return ; } vis[u] = 1; int f = 0; for (pii p : ed[u]) { int v = p.fir, w = p.sec; if (v != fa || f) { st[++top] = mkp(u, v); dfs(v, u); if (ret) return ; top--; } if (v == fa) f = 1; } } map <pair<int, pii>, bool> mm; signed main() { // freopen("wildfire.in", "r", stdin); // freopen("wildfire.out", "w", stdout); int id, T; scanf("%lld %lld", &id, &T); while (T--) { scanf("%lld %lld %lld", &n, &m, &l); for (int i = 1; i <= n; i++) { ed[i].clear(); } for (int i = 1; i <= m; i++) { int u, v, w; scanf("%lld %lld %lld", &u, &v, &w); ed[u].push_back(mkp(v, w)); ed[v].push_back(mkp(u, w)); } top = 0; memset(vis, 0, sizeof vis); ret = 0; dfs(1, 0); int now = 0; for (int i = 1; i <= n; i++) { for (pii j : ed[i]) { if (!mm[mkp(i, mkp(j.fir, j.sec))]) { now++; a[now].val = j.sec; if (mp[mkp(i, j.fir)]) { a[now].b = 1; } mm[mkp(j.fir, mkp(i, j.sec))] = 1; } } } stable_sort(a + 1, a + m + 1, cmp); int c1 = 0, c2 = 0; //环上的最小和次小 for (int i = 1; i <= m; i++) { if (!c1 && a[i].b) { c1 = i; continue; } if (!c2 && a[i].b) { c2 = i; break; } } int sz = m; if (c1 && c2) { sz--; swap(a[m], a[c1]); a[c2].val += a[m].val; stable_sort(a + 1, a + sz + 1, cmp); } int res = 0; for (int i = 1; i <= sz; i++) { if (l < (i - 1) * (a[i].val - a[i - 1].val)) { res = a[i - 1].val + l / (i - 1); l = 0; break; } l -= (i - 1) * (a[i].val - a[i - 1].val); res = a[i].val; } if (l) res += l / sz; printf("%lld\n", res); } fclose(stdout); return 0; } /* 0 2 3 3 3 1 2 3 2 1 5 1 3 7 4 4 4 1 2 3 2 3 4 3 1 6 2 4 7 */