#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; 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 (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); cout<<n<<" "<<m<<" "<<l<<endl; 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[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); int now = 0; bool r2 = 0; if (d1 && d2 && !ret && n == m) r2 = 1; for (int i = 1; i <= n; i++) { int kk = 0; for (pii j : ed[i]) { if (r2 && i == d1) { // printf("cccccccccc\n"); if (kk && j.fir == d2) { // printf("kkk\n"); a[kk].val += j.sec; // printf("%lld\n", a[kk].val); } else { a[++now].val = j.sec; a[now].b = (j.fir == d2); // printf("js %lld\n", j.sec); } if (!kk && j.fir == d2) { kk = now; // printf("kk %lld\n", kk); } } else if (r2 && i == d2) { if (j.fir != d1) { a[++now].val = j.sec; a[now].b = 0; } } else if (!mm[mkp(i, mkp(j.fir, j.sec))]) { now++; a[now].val = j.sec; a[now].b = 0; 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 - 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; if (r2) { sz--; } if (c1 && c2) { sz--; swap(a[m], a[c1]); a[c2].val += a[m].val; stable_sort(a + 1, a + sz + 1, cmp); } // printf("aaa %lld\n", a[1].val); int res = a[1].val; // printf("szzzzz%lld\n", sz); for (int i = 2; 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; }