#include "swap.h"
//OP
#include<bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define pi pair<int, int >
#define pq priority_queue
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define mset multiset
#define F first
#define S second
using namespace std;
const int K = 23;
int N;
int M;
int id;
int fa[300001];
int val[300001];
int dep[300001];
int back[300001];
int G[300001][2];
int front[300001];
int sp[300001][K];
bool chain[300001];
vector<pair<int, pair<int, int>>> edges;
int find(int x) {return (x == fa[x] ? x : fa[x] = find(fa[x]));}
void dfs(int u, int f) {
if (!u) return;
dep[u] = dep[f] + 1; sp[u][0] = f;
for (int i = 1; i < K; i++) sp[u][i] = sp[sp[u][i-1]][i-1];
for (int child = 0; child < 2; child++) dfs(G[u][child], u);
}
int lca(int u, int v) {
if (dep[v] >= dep[u]) swap(u, v);
for (int i = K - 1; i >= 0; i--)
if (dep[sp[u][i]] >= dep[v]) u = sp[u][i];
if (u == v) return u;
for (int i = K - 1; i >= 0; i--)
if (sp[u][i] != sp[v][i]) u = sp[u][i], v = sp[v][i];
return sp[u][0];
}
void init(int _N, int _M, vector<int> U, vector<int> V, vector<int> W) {
N = _N; M = _M; id = N;
for (int i = 0; i < M; i++) edges.pb({W[i], {U[i], V[i]}});
sort(all(edges));
for (int i = 0; i < 300001; i++) fa[i] = i;
for (int i = 1; i <= N; i++) {chain[i] = 1; front[i] = back[i] = i;}
for (int i = 0; i < M; i++) {
int w = edges[i].F;
int u = edges[i].S.F + 1;
int v = edges[i].S.S + 1;
int A = find(u);
int B = find(v);
if (A == B) {
if (chain[A]) {
int new_id = ++id; fa[A] = new_id;
val[new_id] = w; G[new_id][0] = A;
}
continue;
}
int new_id = ++id; fa[A] = new_id; fa[B] = new_id;
val[new_id] = w; G[new_id][0] = A; G[new_id][1] = B;
if (chain[A] && chain[B]) {
if (front[A] == v || back[A] == v) swap(A, B);
if (front[A] == u) swap(front[A], back[A]);
if (back[B] == v) swap(front[B], back[B]);
if (back[A] == u && front[B] == v) {
chain[new_id] = 1;
front[new_id] = front[A];
back[new_id] = back[B];
}
}
}
dfs(id, 0);
}
int getMinimumFuelCapacity(int X, int Y) {
X++; Y++; int l = lca(X, Y);
if (!chain[l]) return val[l];
for (int i = K - 1; i >= 0; i--)
if (sp[l][i] && chain[sp[l][i]]) l = sp[l][i];
return (l == id ? -1 : val[sp[l][0]]);
}
//ED
