#include<bits/stdc++.h> #define int long long using namespace std; const int maxn=1e6+7; const int Lista[7]={3,4,10,11,13,14,15}; int n,m,L; struct edge{ int u,v,d; }e[maxn]; vector<edge> E[maxn]; bool chk(int S){ int ans=0; for(int i=1;i<=m;i++){ ans+=max(S-e[i].d,0ll); } return ans<=L; } void subA(){ cin>>n>>m>>L; for(int i=1;i<=m;i++)cin>>e[i].u>>e[i].v>>e[i].d; int l=1,r=8e9; while(l<r){ int mid=l+r+1>>1; if(chk(mid))l=mid; else r=mid-1; } cout<<l<<endl; } int id,T; signed main(){ freopen("wildfire.in","r",stdin); freopen("wildfire.out","w",stdout); cin>>id>>T; bool sA=0; if(id==0){ for(int i=1;i<=20;i++)subA(); } else for(int i=0;i<7;i++)if(id==Lista[i])sA=1; if(sA==1){ while(T--)subA(); } }