#include<bits/stdc++.h> using namespace std; struct ldge{ int e,dn; }; bool vis[200005]; priority_queue<int ,vector<int> ,greater<int> > xgpq; vector<ldge> a[200005]; int n,m,l,id,t,k; bool wl(int s){ memset(vis,0,sizeof vis); vis[s]=1; int st=1; if(st==s)st++; queue<int> dot; dot.push(st); vis[st]=1; int cnt = 1; while(!dot.empty()){ int k=dot.front(); dot.pop(); vis[k]=1; /* for(int i = 1;i<=n;i++){ cout<<vis[i]<<" "; } cout<<endl<<k<<endl<<cnt<<endl;*/ cnt++; for(auto b:a[k]){ if(vis[b.e]==1){ continue; } // cout<<b.e<<endl; vis[b.e]=1; dot.push(b.e); } } return cnt==n; } int main(){ //freopen("wildfire.in","r",stdin); //freopen("wildfire.out","w",stdout); cin>>id>>t; while(t--){ cin>>n>>m>>l; memset(a,0,sizeof a); while(m--){ int s,e,w; cin>>s>>e>>w; // cout<<m<<endl; int o = 0; bool f=0; for(auto k:a[s]){ if(k.e==e) { a[s][o].dn+=w; f=1; } o++; } if(f){ o=0; for(auto h:a[e]){ if(h.e==s){ a[s][o].dn+=w; } } } if(!f){a[s].push_back({e,w});a[e].push_back({s,w});} } for(int i = 1;i<=n;i++){ bool k =wl(i); //if(k) } for(int i = 1;i<=n;i++){ for(auto h:a[i]){ if(h.dn==0)continue; xgpq.push(h.dn); } } while((l>0)){ l--; xgpq.push(xgpq.top()+1); xgpq.pop(); } cout<<xgpq.top()<<endl; while(!xgpq.empty()){ xgpq.pop(); } } return 0; }