#include<bits/stdc++.h> using namespace std; #define int long long int idt,T; int n,m,L,u[200005],v[200005],d[200005],loc; vector<pair<int,int>>e[200005]; bool chk(int x){ int sum=0; for(int i=1;i<=m;i++){ if(i==loc)continue; if(d[i]>=x)continue; sum+=x-d[i]; if(sum>L)return 0; } return 1; } void slv1(){ int l=1,r=1e10,mid; while(l<r){ mid=l+r+1>>1; if(chk(mid))l=mid; else r=mid-1; } cout<<l<<endl; return; } int fa[200005][18],dp[200005]; int a,b,did; bool vis[200005]; int id[200005]; void dfs(int p){ // cout<<p<<" "<<fa[p][0]<<endl; vis[p]=1; for(auto x:e[p]){ int to=x.first; if(x.second==loc)continue; if(fa[p][0]==to)continue; if(vis[to]){ a=p; b=to; did=x.second; continue; } fa[to][0]=p; id[to]=x.second; dp[to]=dp[p]+1; dfs(to); } } int lca(int x,int y){ if(dp[x]<dp[y])swap(x,y); int t=dp[x]-dp[y]; for(int i=0;i<18;i++){ // cout<<x<<" "<<y<<endl; if(t>>i&1)x=fa[x][i]; } if(x==y)return x; for(int i=17;i>=0;i--){ // cout<<x<<" "<<y<<endl; if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i]; } return fa[x][0]; } void init(){ for(int i=1;i<=n;i++){ e[i].clear(); for(int j=0;j<18;j++)fa[i][j]=0; vis[i]=0; } loc=0; } void slv2(){ dfs(1); for(int j=1;j<18;j++){ for(int i=1;i<=n;i++){ fa[i][j]=fa[fa[i][j-1]][j-1]; } } int lc=lca(a,b); int mnid=did; for(int i=a;i!=lc;i=fa[i][0]){ if(d[id[i]]<d[mnid])mnid=id[i]; } for(int i=b;i!=lc;i=fa[i][0]){ if(d[id[i]]<d[mnid])mnid=id[i]; } loc=mnid; int lstu=u[mnid],lstv=v[mnid]; for(int i=1;i<=n;i++){ for(int j=0;j<18;j++)fa[i][j]=0; vis[i]=0; } dfs(1); for(int j=1;j<18;j++){ for(int i=1;i<=n;i++){ fa[i][j]=fa[fa[i][j-1]][j-1]; } } lc=lca(lstu,lstv); // cout<<lstu<<" "<<lstv<<" "<<lc<<endl; if(lstu!=lc){ mnid=id[lstu]; lstu=fa[lstu][0]; } else{ mnid=id[lstv]; lstv=fa[lstv][0]; } for(int i=lstu;i!=lc;i=fa[i][0]){ if(d[id[i]]<d[mnid])mnid=id[i]; } for(int i=lstv;i!=lc;i=fa[i][0]){ if(d[id[i]]<d[mnid])mnid=id[i]; } d[mnid]+=d[loc]; slv1(); } void read(int &x){ x=0; char c=getchar(); while(!isdigit(c))c=getchar(); while(isdigit(c))x=x*10+c-'0',c=getchar(); return; } void slv(){ init(); read(n),read(m),read(L); for(int i=1;i<=m;i++){ read(u[i]),read(v[i]),read(d[i]); e[u[i]].push_back({v[i],i}); e[v[i]].push_back({u[i],i}); } if(m==n-1)slv1(); else slv2(); } signed main(){ //freopen("wildfire.in","r",stdin); //freopen("wildfire.out","w",stdout); read(idt),read(T); while(T--)slv(); return 0; }