#include<bits/stdc++.h> using namespace std; #define int long long const int M=2e5+10,mmax=1e10; int n,m,L,ed[M]; 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; } signed main(){ //freopen("wildfire.in","r",stdin); //freopen("wildfire.out","w",stdout); int id,t;cin>>id>>t; while(t--){ 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=10000000000; while(l<r){ int mid=(l+r+1)>>1; if(check(mid))l=mid; else r=mid-1; } cout<<l<<endl; } } return 0; }