#include <bits/stdc++.h> using namespace std; #define int long long #define endl "\n" vector<int>g[200300]; int n,m,L; int U[200300],V[200300],w[200300],fw[200300]; bool ins[200300],vis[200300]; vector<int>R,IR; stack<int>S; inline void dfs(int u,int fid){ ins[u]=1; vis[u]=1; S.push(u); for(int i:g[u])if(i!=fid){ int v=U[i]^V[i]^u; if(!vis[v])fw[v]=w[i],dfs(v,i); else if(ins[v]){ R.push_back(w[i]); while(S.top()!=v){ int x=S.top(); S.pop(); R.push_back(fw[x]); } } } ins[u]=0; if(!S.empty()&&S.top()==u){ if(u!=1)IR.push_back(fw[u]); S.pop(); } } inline bool chk(int k){ int rem=L; for(int x:IR) rem-=max(0ll,k-x); if(!R.empty()){ int p=R.size(); int a=R[0],b=R[1]; for(int i=2;i<p;i++) rem-=max(0ll,k-R[i]); return rem>=0&&a+b+rem>=k; } return rem>=0; } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); // freopen("wildfire.in","r",stdin); // freopen("wildfire.out","w",stdout); int id,t; cin>>id>>t; while(t--){ R.clear(),IR.clear(); cin>>n>>m>>L; for(int i=1;i<=n;i++) g[i].clear(),vis[i]=ins[i]=0; for(int i=1;i<=m;i++){ cin>>U[i]>>V[i]>>w[i]; g[U[i]].push_back(i); g[V[i]].push_back(i); } dfs(1,0); sort(R.begin(),R.end()); sort(IR.begin(),IR.end()); int l=0,r=4e9;//在二元环的时候上界应是4e9，但是这个情况是n=2,当时没想到这种情况，然后拍的时候造数据是大数据。没有尝试生成n=2的数据。 while(l<r){ int mid=l+r+1>>1; if(chk(mid))l=mid; else r=mid-1; } cout<<l<<endl; } cout.flush(); fflush(stdout); return 0; } /* 挂分详见line 66 */