#include "bits/stdc++.h"
#include "swap.h"
using namespace std;
#define ll long long
#define all(v) v.begin(),v.end()
#define sz(v) (int)v.size()
const int N = 3e5 + 5;
const int LOG = 20;
const int INF = 1e9 + 5;
int lift[N][LOG],dp[N],valid[N],deg[N],ptr;
int par[N],siz[N],ind[N];
inline void add_node(int a,int b,int w){
lift[a][0] = lift[b][0] = ptr;
valid[ptr] = max(valid[a], valid[b]);
dp[ptr] = w;
}
int find(int a){
if(par[a] == a) return par[a];
return par[a] = find(par[a]);
}
inline void merge(int a,int b){
a = find(a), b = find(b);
if(a == b) return;
if(siz[a] < siz[b]) swap(a, b);
siz[a] += siz[b];
par[b] = a;
}
inline int Find(int c,int w){
for(int i = LOG - 1; i >= 0; i--) if(dp[lift[c][i]] <= w) c = lift[c][i];
return c;
}
void init(int _N, int _M, vector<int> U, vector<int> V, vector<int> W) {
int n = _N, m = _M;
vector<array<int,3>> edges;
for(int i=0;i<m;i++){
int a = U[i], b = V[i], c = W[i];
edges.push_back({c, a, b});
}
fill(siz,siz+N,1);
iota(par,par+N,0);
iota(ind,ind+N,0);
ptr = n - 1;
sort(all(edges));
for(auto [w, a, b] : edges){
int oa = ind[find(a)], ob = ind[find(b)];
int ok = (find(a) == find(b));
merge(a, b);
ind[find(a)] = ++ptr;
deg[a]++,deg[b]++;
add_node(oa,ob,w);
if(deg[a] >= 3 || deg[b] >= 3 || ok) valid[ptr] = 1;
}
lift[ptr][0] = ptr;
for(int j = 1; j < LOG ; j++) for(int i = 0; i <= ptr; i++) lift[i][j] = lift[lift[i][j-1]][j-1];
}
int getMinimumFuelCapacity(int X, int Y){
int a = X, b = Y;
int l = 0, r = INF;
while(l < r){
int mid = (l + r) / 2;
int ca = Find(a, mid);
int cb = Find(b, mid);
if(ca != cb || !valid[ca]) l = mid + 1;
else r = mid;
}
if(l == INF) return -1;
else return l;
}
/*void _(){
int n,m;
vector<array<int,3>> edges;
cin >> n >> m;
for(int i=0;i<m;i++){
int a,b,c;
cin >> a >> b >> c;
edges.push_back({c, a, b});
}
fill(siz,siz+N,1);
iota(par,par+N,0);
iota(ind,ind+N,0);
ptr = n - 1;
sort(all(edges));
for(auto [w, a, b] : edges){
int oa = ind[find(a)], ob = ind[find(b)];
int ok = (find(a) == find(b));
merge(a, b);
ind[find(a)] = ++ptr;
deg[a]++,deg[b]++;
add_node(oa,ob,w);
if(deg[a] >= 3 || deg[b] >= 3 || ok) valid[ptr] = 1;
}
lift[ptr][0] = ptr;
for(int j = 1; j < LOG ; j++) for(int i = 0; i <= ptr; i++) lift[i][j] = lift[lift[i][j-1]][j-1];
int q; cin >> q;
while(q--){
int a, b; cin >> a >> b;
int l = 0, r = INF;
while(l < r){
int mid = (l + r) / 2;
int ca = Find(a, mid);
int cb = Find(b, mid);
if(ca != cb || !valid[ca]) l = mid + 1;
else r = mid;
}
if(l == INF) cout << -1 << '\n';
else cout << l << '\n';
}
}
int32_t main(){
ios::sync_with_stdio();cin.tie();
int tc=1;//cin >> tc;
while(tc--) _();
}*/
