#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]; set <int> eg[200005]; struct node { int val; //val: 边权，用于计算 bool b; //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 (int v : eg[u]) { 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--) { mm.clear(); mp.clear(); scanf("%lld %lld %lld", &n, &m, &l); for (int i = 1; i <= n; i++) { ed[i].clear(); eg[i].clear(); } int d1 = 0, d2 = 0; 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)); eg[u].insert(v); //eg: 去重之后的边，用于判二元环 eg[v].insert(u); } for (int i = 1; i <= n; i++) { if (!d1 && ed[i].size() - eg[i].size() == 1) { d1 = i; continue; } if (!d2 && ed[i].size() - eg[i].size() == 1) { d2 = i; break; } } top = 0; memset(vis, 0, sizeof vis); ret = 0; dfs(1, 0); //dfs: 用于算环 int now = 0; bool r2 = 0; //r2: 特判二元环 if (d1 && d2 && !ret && n == m) r2 = 1; for (int i = 1; i <= n; i++) { int kk = 0; //kk: 二元环中第一条被计入的边 //具体思路：二元环第二条边的值直接加入第一条边的值 for (pii j : ed[i]) { if (!mm[mkp(i, mkp(j.fir, j.sec))]) //mm: 用于去重建的双向边 { if (r2 && i == d1) //这里为了方便直接将二元环的第一个点连的所有边建上，第二个除了和第一个点连的之外全建 { mm[mkp(j.fir, mkp(i, j.sec))] = 1; if (kk && j.fir == d2) a[kk].val += j.sec; else a[++now].val = j.sec; if (!kk && j.fir == d2) kk = now; } else if (r2 && i == d2) { mm[mkp(j.fir, mkp(i, j.sec))] = 1; if (j.fir != d1) a[++now].val = j.sec; } else { now++; a[now].val = j.sec, a[now].b = 0; if (mp[mkp(i, j.fir)]) //mp: 环上的边 a[now].b = 1; mm[mkp(j.fir, mkp(i, j.sec))] = 1; } } } } stable_sort(a + 1, a + m - r2 + 1, cmp); int c1 = 0, c2 = 0; //环上的最小和次小 if (!r2) { 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 - r2; 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 = a[1].val; for (int i = 2; i <= sz; i++) //核心部分，O(n) 从上一个摊到第 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; } res += l / sz; printf("%lld\n", res); } fclose(stdout); return 0; }