#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ii = pair<int,int>;
using iii = tuple<int,int,int>;
const int inf = 2e9+1;
const int mod = 1e9+7;
const int maxn = 1e5+100;
template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }
vector<tuple<int,int,int>>edges;
int lvl[maxn], par[maxn], when[maxn];
ii pontas[maxn];
vector<int>comp[maxn];
vector<ii>parents[maxn];
int findp(int x){return par[x] = (par[x]==x?x:findp(par[x]));}
void merge(int w,int u,int v){
int pu = findp(u), pv = findp(v), ciclo = 0;
if(lvl[pu]<lvl[pv])swap(pu,pv), swap(u,v);
if(pu==pv)ciclo = 1;
//check if someone's component turned into a non-path component
par[pv] = pu;
if(when[pu]==inf&&when[pv]!=inf){
for(auto x:comp[pu])when[x] = w;
}else if(when[pu]!=inf&&when[pv]==inf){
for(auto x:comp[pv])when[x] = w;
}else if((ciclo||(u!=pontas[pu].first&&u!=pontas[pu].second)||
(v!=pontas[pv].first&&v!=pontas[pv].second))&&when[pu]==inf&&
when[pv]==inf){
for(auto x:comp[pu])when[x] = w;
if(!ciclo)for(auto x:comp[pv])when[x] = w;
}
if(ciclo)return;
for(auto x:comp[pv]){
comp[pu].pb(x);
parents[x].pb({w,pu});
}
if(when[pu]==when[pv]&&when[pu]==inf){
if(pontas[pu].first==u)swap(pontas[pu].first,pontas[pu].second);
if(pontas[pv].first!=v)pontas[pu].second = pontas[pv].first;
else pontas[pu].second = pontas[pv].second;
}
if(lvl[pu]==lvl[pv])++lvl[pu];
}
void init(int N, int M,vector<int> U, vector<int> V, vector<int> W) {
for(int i=0;i<M;++i){
edges.pb({W[i], U[i], V[i]});
}
for(int i=0;i<N;++i){
par[i] = i, pontas[i] = {i,i}, when[i] = inf;
parents[i].pb({0,i}), comp[i].pb(i);
}
sort(all(edges));
for(auto [w,u,v]:edges){
merge(w,u,v);
}
for(int i=0;i<N;++i)reverse(all(parents[i]));
}
int getMinimumFuelCapacity(int X, int Y) {
if(when[X]==inf)return -1;
int last = 0;
while(last!=min(sz(parents[X]), sz(parents[Y]))-1){
if(parents[X][last]!=parents[Y][last])break;
++last;
}
if(parents[X][last].second!=parents[Y][last].second)--last;//corner fudido
auto [custo,pai] = parents[X][last];
ckmax(custo, parents[Y][last].first);
return max(custo, min(when[X], when[Y]));
}
// int main() {
// int N, M;
// assert(2 == scanf("%d %d", &N, &M));
// std::vector<int> U(M), V(M), W(M);
// for (int i = 0; i < M; ++i) {
// assert(3 == scanf("%d %d %d", &U[i], &V[i], &W[i]));
// }
// int Q;
// assert(1 == scanf("%d", &Q));
// std::vector<int> X(Q), Y(Q);
// for (int i = 0; i < Q; ++i) {
// assert(2 == scanf("%d %d", &X[i], &Y[i]));
// }
// init(N, M, U, V, W);
// std::vector<int> minimum_fuel_capacities(Q);
// for (int i = 0; i < Q; ++i) {
// minimum_fuel_capacities[i] = getMinimumFuelCapacity(X[i], Y[i]);
// }
// for (int i = 0; i < Q; ++i) {
// printf("%d\n", minimum_fuel_capacities[i]);
// }
// return 0;
// }
