#include <bits/stdc++.h> #define int long long using namespace std; int id,t,n,m,l; int a[200005],h[200005],cnt; struct edge { int u,v,w; int nxt; } e[200005]; inline void add (int u,int v,int w) { cnt++; e[cnt].u = u; e[cnt].v = v; e[cnt].w = w; e[cnt].nxt = h[u]; h[u] = cnt; } bool vis[200005]; stack <int> st; vector <int> vec; void dfs (int E) { int lst = e[E].u,u = e[E].v; st.push(E); vis[u] = 1; for (int i = h[u];i;i = e[i].nxt) { int v = e[i].v; if (v == lst) { continue; } if (vis[v]) { while (!st.empty()) { vec.push_back(st.top()); if (e[st.top()].u == v) { break; } st.pop(); } return; } dfs(i); } st.pop(); return; } signed main () { cin >> id >> t; e[0].u = 0; e[0].v = 1; while (t--) { memset(a,0,sizeof(a)); memset(e,0,sizeof(e)); memset(vis,0,sizeof(vis)); memset(h,0,sizeof(h)); while (!st.empty()) { st.pop(); } vec.clear(); cin >> n >> m >> l; for (int i = 1;i <= m;i++) { int u,v; cin >> u >> v; cin >> a[i]; add(u,v,a[i]); add(v,u,a[i]); } if (vec.size()) { int mn = 1e10,mn2 = 1e10; for (auto i : vec) { if (e[i].w < mn) { mn = i; } else { if (e[i].w < mn2) { mn2 = i; } } } a[mn2 / 2] += a[mn / 2]; a[mn / 2] = 1e10; m--; } int x = 1; a[m + 1] = 1e10; sort(a + 1,a + m + 1); for (int i = 1;i <= m;i++) { cout << a[i] << ' '; } cout << endl; while (1) { x = upper_bound(a + x + 1,a + m + 1,a[x]) - a; if ((x - 1) * (a[x] - a[x - 1]) > l) { break; } l -= (x - 1) * (a[x] - a[x - 1]); } if (x <= m) { cout << a[x - 1] << endl; } else { cout << a[x - 1] + (l / m) << endl; } } return 0; }