#include "swap.h"
// author: yanybayev
#include "bits/stdc++.h"
using namespace std;
#define ff first
#define ss second
#define pp pop_back
#define ll long long
#define pb push_back
#define ls(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define wr cout << "------------------------" << endl
const int LOG = 21;
const int N = 3e5 + 5;
int par[N];
vector<int> g[N];
int good[N];
int val[N];
int id;
int depth[N];
int up[N][LOG];
int end1[N];
int end2[N];
int find(int x) {
if (x == par[x]) return x;
return par[x] = find(par[x]);
}
void merge(int a, int b, int c) {
int _a, _b;
_a = a, _b = b;
a = find(a); b = find(b);
if (a == b) {
g[id].pb(a);
par[a] = par[id] = id;
good[id] = 1;
val[id] = c;
}
else {
g[id].pb(a); g[id].pb(b);
par[a] = par[b] = par[id] = id;
val[id] = c;
int isenda = (end1[a] == _a or end2[a] == _a);
int isendb = (end1[b] == _b or end2[b] == _b);
if (!good[a] and !good[b] and isenda and isendb) {
good[id] = false;
end1[id] = (_a == end1[a] ? end2[a] : end1[a]);
end2[id] = (_b == end1[b] ? end2[b] : end1[b]);
}
else good[id] = true;
}
id += 1;
}
int LCA(int a, int b) {
if (depth[a] < depth[b]) swap(a, b);
for (int i = LOG - 1; ~i; -- i) {
if (depth[a] - (1 << i) >= depth[b]) {
a = up[a][i];
}
}
if (a == b) return a;
for (int i = LOG - 1; ~i; -- i) {
if (up[a][i] != up[b][i]) {
a = up[a][i];
b = up[b][i];
}
}
return up[a][0];
}
void dfs(int nd, int p, int d) {
depth[nd] = d;
up[nd][0] = p;
for (int i = 1; i < LOG; ++ i) up[nd][i] = up[up[nd][i - 1]][i - 1];
for (auto it : g[nd]) dfs(it, nd, d + 1);
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
id = N + 1;
for (int i = 1;i<=N;++i) {
par[i] = end1[i] = end2[i] = i;
}
vector<array<int, 3>> edges;
for (int i = 0; i < M; ++ i) edges.pb({W[i], U[i] + 1, V[i] + 1});
sort(all(edges));
for (auto [c, a, b] : edges) {
merge(a, b, c);
}
dfs(id - 1, id - 1, 1);
}
int getMinimumFuelCapacity(int X, int Y) {
X += 1, Y += 1;
int L = LCA(X, Y);
int cur = L;
if (!good[cur]) {
for (int i = LOG - 1; ~i; -- i) {
if (!good[up[cur][i]]) {
cur = up[cur][i];
}
}
cur = up[cur][0];
}
if (good[cur]) return val[cur];
return -1;
}
