//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 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 dfn[N],low[N];int dfncnt=0; stack<int> dt; void dfs(int u,int fa){ dfn[u]=++dfncnt;low[u]=dfncnt; vis[u]=1;int res=0;dt.push(u); for(auto ed:e[u]){ int v=ed.to;int cnt=0; if(v==fa) cnt++; if(dfn[v]&&(v!=fa||cnt>1)){ low[u]=min(dfn[v],low[u]); }if(!vis[v]){ dfs(v,u);low[u]=min(low[u],low[v]); } } if(low[u]==dfn[u]){ int dcnt=0; if(dt.top()==u){ dt.pop(); }else{ while(!dt.empty()){ int p=dt.top();dt.pop(); in_ring[p]=1; if(p==u) continue; } } } } 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,n) in_ring[i]=0;dfncnt=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;e[u].jp8((edge){u,v,i,w}),e[v].jp8((edge){v,u,i,w}); }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(in_ring[E[i].fr]&&in_ring[E[i].to]){ in_rng[++tp_rng]=E[i].val; }else{ in_tre[++tp_tre]=E[i].val; } }assert(tp_rng!=1); sort(in_rng+1,in_rng+tp_rng+1); 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<<endl; } } int main(){ int sub,t;cin>>sub>>t; while(t--) slv(); return 0; }