#include<bits/stdc++.h> using namespace std; const int N = 2e5+10; #define int long long int id,T,n,m,l,w[N],d[N],vis[N]; vector<pair<int,int> > G[N]; pair<int,int> lst[N]; bool flag=false; void dfs(int x,pair<int,int> last){ if(vis[x]){ while(1){ w[last.second]=1; if(last.first==x) break; last=lst[last.first]; } flag=true; return; } vis[x]=1; lst[x]=last; for(int i=0;i<G[x].size();i++){ int v=G[x][i].first,z=G[x][i].second; if(G[x][i]!=last){ dfs(v,make_pair(x,z)); if(flag) return; } } } bool check(int x){ int cnt=0; for(int i=1;i<=m;i++){ if(w[i]==0){ cnt=cnt+max(x-d[i],(long long)0); } } int minn=2e9,minn_2=2e9,bz=0,bz_2=0; for(int i=1;i<=m;i++){ if(w[i]==1){ if(minn>d[i]){ minn_2=minn; bz_2=bz; bz=i; minn=d[i]; } else if(minn_2>d[i]){ bz_2=i; minn_2=d[i]; } } } if(bz!=0&&bz_2!=0) cnt=cnt+max(x-minn_2-minn,(long long)0); else bz=0,bz_2=0; for(int i=1;i<=m;i++){ if(w[i]==1&&i!=bz&&i!=bz_2){ cnt=cnt+max(x-d[i],(long long)0); } } if(cnt<=l) return true; else return false; } signed main(){ ios::sync_with_stdio(false); cin>>id>>T; while(T--){ flag=false; cin>>n>>m>>l; for(int i=1;i<=m;i++) vis[i]=0; for(int i=1;i<=m;i++) lst[i]=make_pair(0,0); for(int i=1;i<=m;i++){ int x,y,v; cin>>x>>y>>v; d[i]=v; G[x].push_back(make_pair(y,i)); G[y].push_back(make_pair(x,i)); } dfs(1,make_pair(-1,-1)); int L=1,R=2e9,ans; while(L<=R){ int mid=(L+R)/2; if(check(mid)){ L=mid+1; ans=mid; } else R=mid-1; } cout<<ans<<endl; //for(int i=1;i<=m;i++) if(w[i]==1) cout<<i<<" "; //cout<<endl; } return 0; }