#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) { // if (top == 0) // { // printf("nmslccf\n"); // fclose(stdout); // } mp[mkp(st[top].fir, st[top].sec)] = 1; mp[mkp(st[top].sec, st[top].fir)] = 1; // printf("huan shang %lld %lld\n", st[top].fir, st[top].sec); top--; } mp[mkp(st[top].fir, st[top].sec)] = 1; mp[mkp(st[top].sec, st[top].fir)] = 1; // printf("huan shang %lld %lld\n", st[top].fir, st[top].sec); ret = 1; return ; } vis[u] = 1; int f = 0; for (pii p : ed[u]) { int v = p.fir, w = p.sec; // printf(" %lld %lld %lld\n", u, v, w); if (v != fa || f) { st[++top] = mkp(u, v); // printf(" %lld->%lld\n", u, v); dfs(v, u); if (ret) return ; top--; } if (v == fa) f = 1; } } signed main() { 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]) { now++; a[now].val = j.sec; if (mp[mkp(i, j.fir)]) { a[now].b = 1; // printf("nofndsbn\n"); } } } stable_sort(a + 1, a + m + 1, cmp); bool used = 0, u2 = 0; int cnt = 1, res = a[1].val; int strt = 2; int ad = 0; if (a[1].b) { // printf("dao %lld jian diao\n", a[1].val); ad = a[1].val; used = 1; strt = 3; res = a[2].val; } for (int i = strt; i <= m; i++) { if (!used && a[i].b) { // printf("dao %lld jian diao\n", a[i].val); used = 1; ad = a[i].val; a[i].val = a[i - 1].val; continue; } if (!u2 && a[i].b) { // printf("u2 %lld\n", a[i].val); u2 = 1; a[i].val += ad; stable_sort(a + i, a + m + 1, cmp); } if (l < cnt * (a[i].val - a[i - 1].val)) { int x = l / cnt; res = a[i - 1].val + x; l = 0; break; } l -= cnt * (a[i].val - a[i - 1].val); res = a[i].val; cnt++; } if (l) { res += l / cnt; } 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 */