#include <bits/stdc++.h> #define int long long using namespace std; int id,t,n,m,l; int a[200005]; signed main () { cin >> id >> t; while (t--) { memset(a,0,sizeof(a)); cin >> n >> m >> l; for (int i = 1;i <= m;i++) { int u,v; cin >> u >> v; cin >> a[i]; } sort(a + 1,a + m + 1); int f = 1; if (m == n) { f = 2; } a[m + 1] = 1e10; int x = f; while (1) { x = upper_bound(x + 1,m + 1,a[x]); if ((x - 1) * (a[x] - a[x - 1]) > l) { break; } l -= (x - 1) * (a[x] - a[x - 1]); } if (x <= m) { cout << a[x - 1] << endl; } else { cout << a[x - 1] + (l / m) << endl; } } return 0; }