#include<bits/stdc++.h> #define int long long using namespace std; int n,m,k; map<pair<int,int>,int>mp; vector<pair<int,int> >a; int ti[200010]; int __,_; bool check(int mid){ int sum=0; int nm=m; for(int i=1;i<=m;i++){ if(ti[i]<mid)sum+=mid-ti[i]; else { nm=i-1; break; } } if(sum<=k||nm==1)return 1; sum-=mid-ti[1]; sum-=min(mid-ti[2],ti[1]); if(sum<=k)return 1; sum+=mid-ti[1]; sum+=min(mid-ti[2],ti[1]); for(int i=2;i<=nm;i++){ sum-=mid-ti[i]; sum-=min(mid-ti[1],ti[i]); if(sum<=k)return 1; sum+=mid-ti[i]; sum+=min(mid-ti[1],ti[i]); } return 0; } signed main(){ cin>>__>>_; while(_--){ mp.clear(); a.clear(); cin>>n>>m>>k; for(int i=1;i<=m;i++){ int x,y,w; cin>>x>>y>>w; pair<int,int>tmp=make_pair(x,y),tmp2=make_pair(y,x); if(mp[tmp]==0&&mp[tmp2]==0){ a.push_back(tmp); } mp[tmp]+=w; mp[tmp2]+=w; } m=a.size(); if(m==n-1){ for(int i=0;i<m;i++){ ti[i+1]=mp[a[i]]; } sort(ti+1,ti+1+m); int l=1,r=0x7f7f7f7f; while(l!=r){ int mid=(l+r+1)>>1; int sum=0; for(int i=1;i<=m;i++)if(ti[i]<mid)sum+=mid-ti[i]; if(sum>k){ r=mid-1; }else l=mid; } cout<<l<<endl; }else if(m==n){ for(int i=0;i<m;i++){ ti[i+1]=mp[a[i]];· } sort(ti+1,ti+1+m); int l=1,r=0x7f7f7f7f; while(l!=r){ int mid=(l+r+1)>>1; if(check(mid)){ l=mid; }else r=mid-1; } cout<<l<<endl; }else{ cout<<0<<endl; } } }