#include<bits/stdc++.h> #define ll long long using namespace std; const int maxn=2e5+10; const ll inf=1e9; const ll mod=998244353; ll n,m,k,cnt=0,t,l,r,tp=0,id,mn,mn1; ll a[maxn],b[maxn],suma[maxn],sumb[maxn],vis[maxn],vis1[maxn]; vector< pair<int,pair<int,ll> > > q[maxn]; bool dfs(int pos,int from){ int siz=q[pos].size(); vis[pos]=1; for(int i=0;i<siz;i++){ int v=q[pos][i].first; ll w=q[pos][i].second.second; ll id=q[pos][i].second.first; if(v==from&&vis1[id]) continue; vis1[id]=1; if(vis[v]){ if(mn>w) swap(w,mn); if(mn1>w) swap(mn1,w); vis[v]=0; return 1; } if(dfs(v,pos)){ if(mn>w) swap(w,mn); if(mn1>w) swap(mn1,w); return vis[pos]; } } return 0; } int main(){ // freopen("wildfire.in","r",stdin); // freopen("wildfire.out","w",stdout); scanf("%lld%lld",&id,&t); while(t--){ scanf("%lld%lld%lld",&n,&m,&k); for(int i=1;i<=n;i++) q[i].clear(); for(int i=1;i<=m;i++){ ll l,r; scanf("%lld%lld%lld",&l,&r,&a[i]); q[l].push_back(make_pair(r,make_pair(i,a[i]))); q[r].push_back(make_pair(l,make_pair(i,a[i]))); vis[l]=vis[r]=vis1[i]=0; } if(m==n-1){ sort(a+1,a+1+m); ll num=1,ans=a[1]; for(int i=2;i<=m;i++){ if(k<num*(a[i]-ans)){ ans+=k/num; k=0; break; } k-=num*(a[i]-ans); num++,ans=a[i]; } printf("%lld\n",ans+k/m); continue; } mn=mn1=inf; tp=0; dfs(1,0); // cout<<mn<<" "<<mn1<<endl;sudo mount -t fuse.vmhgfs-fuse .host:/ /mnt/hgfs -o allow_other for(int i=1;i<=m;i++){ if(a[i]==mn1&&tp==0) a[i]=inf,tp=1; if(a[i]==mn) a[i]+=mn1,mn=inf; } sort(a+1,a+1+m); m--; ll num=1,ans=a[1]; for(int i=2;i<=m;i++){ if(k<num*(a[i]-ans)){ ans+=k/num; k=0; break; } k-=num*(a[i]-ans); num++,ans=a[i]; } printf("%lld\n",ans+k/m); } fclose(stdin); fclose(stdout); return 0; }