#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back using namespace std; typedef long long ll; const int maxn=2e5+10,mod=998244353; inline ll read(){ ll x=0;short t=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,m,L,s[maxn],vis[maxn],tg; pi lst[maxn]; vector<pi>v[maxn]; vector<int>G,E; bool Evis[maxn]; bool cmp(int x,int y){return s[x]<s[y];} void dfs(int u,pi fa){ if(vis[u]){ //cout<<"? "<<u<<endl; while(1){ G.p_b(fa.p2); if(fa.p1==u)break; fa=lst[fa.p1]; }tg=1;return; }lst[u]=fa,vis[u]=1; for(auto it:v[u])if(it!=fa){ dfs(it.p1,m_p(u,it.p2)); if(tg)return; } } bool chk(ll w){ ll all=0; for(int x:E)all+=max(w-s[x],0ll); if(G.empty())return (all<=L); int sz=G.size(); for(int i=2;i<sz;++i)all+=max(w-s[G[i]],0ll); all+=max(w-(s[G[0]]+s[G[1]]),0ll); return (all<=L); } void slv(){ n=read(),m=read(),L=read(); up(i,1,n)v[i].clear(),vis[i]=tg=0; G.clear(),E.clear();up(i,1,m)Evis[i]=0; up(i,1,m){ int x=read(),y=read(),w=read();s[i]=w; v[x].p_b(m_p(y,i)),v[y].p_b(m_p(x,i)); }dfs(1,m_p(-1,-1));sort(G.begin(),G.end(),cmp); for(int x:G)Evis[x]=1;up(i,1,m)if(!Evis[i])E.p_b(i); ll l=0,r=4e9; while(l+1<r){ ll mid=l+r>>1; if(chk(mid))l=mid; else r=mid; }printf("%lld\n",l); }int main(){ //freopen("wildfire.in","r",stdin); //freopen("wildfire.out","w",stdout); read();int t=read();while(t--)slv(); fclose(stdin); fclose(stdout); //cerr<<clock()*1.0/CLOCKS_PER_SEC<<"s\n"; return 0; }