//mid ll->int //id->fr-to #include<bits/stdc++.h> #define Rf(i,a,b) for(int i=(a);i<=(b);i++) #define Rb(i,a,b) for(int i=(a);i>=(b);i--) #define jp8 push_back #define ll long long #define PII pair<int,int> #define mpx make_pair #define int ll using namespace std; const int N=2e5+10; bool vis[N];bool in_ring[N]; struct edge{ int fr,to,id,val; }E[N]; vector<edge> e[N]; map<PII,int> q; int n,m;ll L; int dfs(int u,int fa){ vis[u]=1;int res=0; for(auto ed:e[u]){ int v=ed.to;int cnt=0; if(v==fa) cnt++; if(vis[v]&&(v!=fa||cnt>1)){ res|=v;in_ring[ed.id]=1; }if(!vis[v]){ int tmp=dfs(v,u); if(tmp!=0) in_ring[ed.id]=1; res|=tmp; } }if(res==u) res=0; return res; } ll in_tre[N];int tp_tre=0; ll in_rng[N];int tp_rng=0; bool chk(ll k){ ll cost=0; Rf(i,1,tp_tre){//cout<<in_tre[i]<<' '; if(in_tre[i]<k) cost+=(k-in_tre[i]); }Rf(i,2,tp_rng){ if(in_rng[i]<k) cost+=(k-in_rng[i]); }//cout<<k<<' '<<cost<<endl; if(cost<=L) return 1; else return 0; } void slv(){ cin>>n>>m>>L;q.clear();//cout<<n<<' '<<m<<' '<<L<<' '; Rf(i,1,n) vis[i]=0;Rf(i,1,m) in_ring[i]=0; Rf(i,1,n) e[i].clear(); Rf(i,1,m){ int u,v,w;cin>>u>>v>>w; edge tmp={u,v,i,w}; E[i]=tmp;if(q[mpx(u,v)]==0) e[u].jp8((edge){u,v,i,w}),e[v].jp8((edge){v,u,i,w}); q[mpx(u,v)]++;q[mpx(v,u)]++; }dfs(1,0); int fl=1;Rf(i,1,n) fl&=vis[i]; if(fl==0||n==1){ cout<<0<<endl; }else{ tp_tre=0;tp_rng=0; Rf(i,1,m){ if(max(q[mpx(E[i].fr,E[i].to)],q[mpx(E[i].to,E[i].fr)])>=2){ in_ring[E[i].id]=1; } } Rf(i,1,m){ //cout<<in_ring[i]<<' '; if(in_ring[i]){ in_rng[++tp_rng]=E[i].val; }else{ in_tre[++tp_tre]=E[i].val;//cout<<E[i].val<<' '; } }assert(tp_rng!=1); sort(in_rng+1,in_rng+tp_rng+1);//cout<<endl; if(tp_rng>=2) in_rng[2]+=in_rng[1]; ll l=1,r=4e9+20; while(l<r){ ll mid=(l+r+1)/2; if(chk(mid)) l=mid; else r=mid-1; //cout<<l<<' '<<r<<endl; }cout<<l<<endl; } } signed main(){ int sub,t;cin>>sub>>t; while(t--) slv(); return 0; }