#include "swap.h"
#include <bits/stdc++.h>
#define FAST_IO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define setIO(i, o) freopen(i, "r", stdin), freopen(o, "w", stdout)
#define rand_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int) (x).size()
#define lc(i) 2*i
#define rc(i) 2*i+1
//#define int long long
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vii = vector<ii>;
using vi = vector<int>;
using vvi = vector<vi>;
using vb = vector<bool>;
using vvb = vector<vb>;
//rand_init;
const int MAXN = 2e5 + 5, MOD = 1e9 + 7, INF = 1e9 + 5;
struct Edge {
int u, v, w;
Edge(int u, int v, int w) : u(u), v(v), w(w) {}
bool operator<(const Edge &other) {
return w < other.w;
}
};
int n, m, fakeNode, timer = 0;
const int MAXK = 20;
vector<Edge> edges;
vi g[MAXN];
int par[MAXN], cost[MAXN], deg[MAXN], binlift[MAXN][MAXK], minCost[MAXN], tin[MAXN], tout[MAXN];
bool valid[MAXN];
void addEdge(int u, int w) {
g[u].pb(fakeNode);
g[fakeNode].pb(u);
cost[fakeNode] = w;
valid[fakeNode] |= valid[u];
}
int get(int x) {
return (par[x] == x ? x : par[x] = get(par[x]));
}
void unite(int x, int y, int w) {
// cout << "Edge unite: " << x << " " << y << " " << w << "\n";
int u = get(x), v = get(y);
deg[x]++;
deg[y]++;
valid[u] |= (deg[x] >= 3);
valid[v] |= (deg[y] >= 3);
u = get(u), v = get(v);
if (u == v) {
addEdge(u, w);
par[u] = fakeNode;
valid[fakeNode] = true;
fakeNode++;
return;
}
addEdge(u, w);
addEdge(v, w);
par[u] = fakeNode;
par[v] = fakeNode;
fakeNode++;
}
void dfs(int u = fakeNode, int p = -1) {
if (valid[u]) minCost[u] = cost[u];
if (p != -1) {
binlift[u][0] = p;
minCost[u] = min(minCost[u], minCost[p]);
}
tin[u] = timer++;
for (int j = 1; j < MAXK; j++) {
if (binlift[u][j - 1] < 0) continue;
binlift[u][j] = binlift[binlift[u][j - 1]][j - 1];
}
for (const auto &v : g[u])
if (v != p)
dfs(v, u);
tout[u] = timer - 1;
}
bool isAnc(int x, int y) {
return (tin[x] <= tin[y] && tout[x] >= tout[y]);
}
int queryLCA(int u, int v) {
if (isAnc(u, v)) return u;
if (isAnc(v, u)) return v;
for (int j = MAXK - 1; j >= 0; j--)
if (binlift[u][j] > -1 && !isAnc(binlift[u][j], v))
u = binlift[u][j];
assert(binlift[u][0] > -1);
return binlift[u][0];
}
void init(int N, int M, vi U, vi V, vi W) {
n = N, m = M;
for (int i = 0; i < m; i++)
edges.eb(U[i], V[i], W[i]);
sort(all(edges));
// Initialise UFDS stuff
iota(par, par + 2 * n, 0);
fakeNode = n;
for (const auto &[u, v, w] : edges)
unite(u, v, w);
for (int i = 0; i < MAXN; i++)
minCost[i] = INF;
for (int i = 0; i <= 2 * n; i++) {
for (int j = 0; j < MAXK; j++) {
binlift[i][j] = -1;
}
}
fakeNode--;
dfs();
}
int getMinimumFuelCapacity(int X, int Y) {
int lca = queryLCA(X, Y);
// cout << "LCA: " << lca << "\n";
return (minCost[lca] < INF ? minCost[lca] : -1);
}
//void solve() {
// int a, b;
// cin >> a >> b;
// vi u(b), v(b), wt(b);
//
// for (int i = 0; i < b; i++)
// cin >> u[i] >> v[i] >> wt[i];
//
// init(a, b, u, v, wt);
//
// int q;
// cin >> q;
// while (q--) {
// int x, y;
// cin >> x >> y;
// cout << getMinimumFuelCapacity(x, y) << "\n";
// }
//}
//
//signed main() {
// FAST_IO;
//#ifdef arujbansal_local
// setIO("input.txt", "output.txt");
//#endif
//
// int tc = 1;
//// cin >> tc;
// while (tc--) solve();
//}
