#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; } void dfs(int u){//找环 if(visn[u]){ while(!q.empty()){ int i=q.top(); cir[++circnt]=i; 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/2])continue; vise[i/2]=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=2;i<=CNT;i++){ //cout<<i<<endl; if(!del[i/2]){//树边 if(e[i].u>=e[i].v)continue; //cout<<"!"<<i<<endl; sum+=max(0ll,mid-e[i].d); } } for(int i=1;i<=circnt;i++){//环上的边 int j=cir[i]; if(j!=x&&j!=y){//不是最小的或次小的边 sum+=max(0ll,mid-e[j].d); //cout<<"?"<<i<<endl; } } sum+=max(0ll,mid-e[x].d-e[y].d); //cout<<mid<<" "<<sum<<endl; return sum<=L; } inline void init(){ CNT=1;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)); memset(del,0,sizeof(del)); 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;} del[cir[i]/2]=1; // if(e[j+1].u==e[j].v&&e[j+1].v==e[j].u&&e[j+1].d==e[j].d){cout<<"&&"<<j<<" "<<j+1<<endl;del[j+1]=1;} // else {cout<<"^^"<<j-1<<" "<<j<<endl;del[j-1]=1;} }//cout<<endl; //cout<<x<<" "<<y<<endl<<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 */ /* 0 1 2 2 2 1 2 1 1 2 1 */