#include<bits/stdc++.h> using namespace std; #define int long long const int M=2e5+10,mmax=3e9; int n,m,L,min1,min2,x,y,ed[M],cir[M],circnt; bool flag,vise[M],visn[M],visc[M],del[M]; stack<int>q; struct Edge{int u,v,d,nxt;}e[M<<1];int CNT,h[M]; void add_side(int u,int v,int d){e[++CNT]=(Edge){u,v,d,h[u]};h[u]=CNT;} bool check(int mid){ int sum=0; for(int i=1;i<=m;i++){ if(ed[i]<mid)sum+=mid-ed[i]; } return sum<=L; } //int dfs(int u){ // if(vis[u])return u;vis[u]=1; // for(inx)if(!vise[i]){ // vise[i]=1; // int tmp=dfs(v); // if(tmp){ // cir[++cnt]=i; // return tmp==u?0:tmp; // } // } // return 0; //} void dfs(int u){//找环 //cout<<u<<endl; if(visn[u]){ while(!q.empty()){ int i=q.top(); cir[++circnt]=i; // cout<<i<<" "<<e[i].u<<" "<<e[i].v<<endl; visc[i]=1; q.pop(); if(e[i].u==u)break; } flag=1; return; }visn[u]=1; for(int i=h[u];i>0;i=e[i].nxt){ if(vise[i])continue; vise[i]=1;int v=e[i].v; if(e[i+1].v==e[i].u&&e[i+1].u==e[i].v&&e[i+1].d==e[i].d)vise[i+1]=1; else vise[i-1]=1; q.push(i); dfs(v); if(flag)return; q.pop(); } } bool check1(int mid){ //cout<<x<<" "<<y<<endl; int sum=0; for(int i=1;i<=CNT;i++){ if(!del[i]){ if(!visc[i]){//树边 if(e[i].u>=e[i].v)continue; //cout<<"!"<<i<<endl; sum+=max(0ll,mid-e[i].d); } else{//环 if(x!=i&&y!=i){//不是最小或次小的边 //cout<<"?"<<i<<endl; sum+=max(0ll,mid-e[i].d); } } } } sum+=max(0ll,mid-e[x].d-e[y].d); //cout<<mid<<" "<<sum<<endl; return sum<=L; } inline void init(){ CNT=0;flag=0;x=y=0;circnt=0; memset(h,-1,sizeof(h)); memset(vise,0,sizeof(vise)); memset(visn,0,sizeof(visn)); memset(visc,0,sizeof(visc)); while(!q.empty())q.pop(); } signed main(){ int id,t;cin>>id>>t; while(t--){ init(); cin>>n>>m>>L; if(m==n-1){ int u,v,l=mmax,r; for(int i=1;i<=m;i++){cin>>u>>v>>ed[i];l=min(l,ed[i]);} if(L==0){cout<<l<<endl;continue;} l=1,r=10000000000ll; while(l<r){ int mid=(l+r+1)>>1; if(check(mid))l=mid; else r=mid-1; } cout<<l<<endl;continue; } int u,v,d,l=mmax,r; for(int i=1;i<=m;i++){ cin>>u>>v>>d; add_side(u,v,d); add_side(v,u,d); l=min(l,d); } dfs(1); min1=min2=mmax;//环上最小的两条边 for(int i=1;i<=circnt;i++){ // cout<<cir[i]<<" "; int d=e[cir[i]].d; if(d<min1){ min2=min1;y=x; min1=d;x=cir[i]; //cout<<"jlafgsjg"<<" "<<x<<" "<<y<<" "<<min1<<" "<<min2<<endl; } else if(d<min2){min2=d;y=cir[i];}//cout<<456343743<<" "<<x<<" "<<y<<" "<<min1<<" "<<min2<<endl;} int j=cir[i]; if(e[j+1].u==e[j].v&&e[j+1].v==e[j].u&&e[j+1].d==e[j].d)del[j+1]=1; else del[j-1]=1; }//cout<<endl; //二分答案 r=mmax; while(l<r){ int mid=(l+r+1)>>1; if(check1(mid))l=mid; else r=mid-1; } cout<<l<<endl; } return 0; } /* 0 2 3 3 3 1 2 3 2 1 5 1 3 7 4 4 4 1 2 3 2 3 4 3 1 6 2 4 7 */