#include<bits/stdc++.h> #define int long long #define doub long double using namespace std; const int maxn=1e6+7; int n,m,L; struct ed{ int v; int id; }; vector<ed> E[maxn]; struct edge{ int u,v,d,id; }e[maxn]; bool incyc[maxn]; vector<edge> cyc; bool mg[maxn]; bool vis[maxn]; int dfs(int u,int las){ if(vis[u])return u; vis[u]=1; for(auto s:E[u]){ if((las^1)==s.id)continue; int ret=dfs(s.v,s.id); if(ret){ incyc[s.id>>1]=1; return ret==u?0:ret; } } return 0; } bool cmp(edge x,edge y){ return x.d<y.d; } bool chk(int S){ int T=0; int ans=0; for(int i=1;i<=m;i++){ if(mg[i]){ T+=e[i].d; continue; } ans+=max(S-e[i].d,0ll); } ans+=max(S-T,0ll); return ans<=L; } void slv(){ cyc.clear(); cin>>n>>m>>L; for(int i=1;i<=n;i++)incyc[i]=mg[i]=vis[i]=0,E[i].clear(); for(int i=1;i<=m;i++){ int u,v,d; cin>>u>>v>>d; E[u].push_back((ed){v,i<<1}); E[v].push_back((ed){u,i<<1|1}); e[i]=(edge){u,v,d,i}; } dfs(1,0); for(int i=1;i<=m;i++)if(incyc[i])cyc.push_back(e[i]); if(cyc.size())sort(cyc.begin(),cyc.end(),cmp); if(cyc.size())for(int i=0;i<2;i++)mg[cyc[i].id]=1; int l=1,r=4e9; while(l<r){ int mid=l+r+1>>1; if(chk(mid))l=mid; else r=mid-1; } cout<<l<<endl; return; } signed main(){ int id,T; cin>>id>>T; while(T--)slv(); } /* 2 3 5 5 2 2 3 3 4 1 1 5 4 4 3 2 4 3 5 2 5 5 0 4 2 2 1 4 2 2 5 1 4 3 3 5 1 4 5 4 2 3 5 3 3 4 5 1 2 1 4 1 2 */