#include<bits/stdc++.h> #define int long long using namespace std; int n,m,extra,l,id,t,dfn[500010],dfntot; struct node{ int u,v,d,i; }e[500100]; vector<int> E[500010]; vector<int> Can_be_Replace; bool vis[500010]; bool cmp(node a,node b){ return a.d<b.d; }bool cmp2(int a,int b){ return e[a].d>e[b].d; }bool cmp3(int a,int b){ return e[a].d<e[b].d; } void dfs(int u,int id_father_edge){ //cout<<u<<' '<<id_father_edge<<'\n'; dfn[u]=++dfntot; for(auto v:E[u]){ if(dfn[e[v].v]){ if(e[id_father_edge].i!=e[v].i){ extra=e[v].i; }continue; }else{ dfs(e[v].v,e[v].i); } }if(dfn[e[extra].u]<dfn[e[extra].v]){ swap(e[extra].u,e[extra].v); } if(dfn[e[extra].v]<dfn[u]&&dfn[e[extra].u]>=dfn[u]){ Can_be_Replace.push_back(id_father_edge); } }signed main(){ ios::sync_with_stdio(0); //freopen("wildfire.in","r",stdin); //freopen("wildfire.out","w",stdout); cin>>id>>t; while(t--){ cin>>n>>m>>l; //if(t==12) cout<<n<<' '<<m<<' '<<l<<'\n'; for(int i=1;i<=n;i++){ E[i].clear(); dfn[i]=0; }dfntot=extra=0; Can_be_Replace.clear(); for(int i=1;i<=m;i++){ cin>>e[i].u>>e[i].v>>e[i].d; //if(t==12) cout<<e[i].u<<' '<<e[i].v<<' '<<e[i].d<<'\n'; e[i].i=i; e[i+m]=e[i];swap(e[i+m].u,e[i+m].v); E[e[i].u].push_back(i); E[e[i].v].push_back(i+m); }for(int i=1;i<=n;i++){ sort(E[i].begin(),E[i].end(),cmp2); }dfs(1,0); //cout<<'\n'; bool flag=0; for(int i=1;i<=n;i++){ if(dfn[i]==0) flag=1; }if(flag){ cout<<0<<'\n'; continue; }else{ if(extra){ Can_be_Replace.push_back(extra); sort(Can_be_Replace.begin(),Can_be_Replace.end(),cmp3); e[Can_be_Replace[1]].d+=e[Can_be_Replace[0]].d; extra=e[Can_be_Replace[0]].i+m; }sort(e+1,e+m+1,cmp); int nowans=0,nowcnt=0; for(int i=1;i<=n;i++){ if(e[i].i==e[extra].i) continue; //cout<<e[i].i<<' '<<e[i].d<<'\n'; if(l>=nowcnt*(e[i].d-nowans)){ l-=nowcnt*(e[i].d-nowans); nowans=e[i].d; nowcnt++; }else{ break; } }nowans+=l/nowcnt; //cout<<extra<<' '<<minnid<<" Q\n"; cout<<nowans<<'\n'; } } }