#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> bin;
vector<int> depvi;
const int logn = 20;
vector<int> w;
vector<int> alledges;
vector<bool> lin;
int n;
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
w = W;
n = N;
vector<int> dsu(N);
iota(dsu.begin(), dsu.end(), 0);
function<int(int)> par = [&](int cur) {
if (dsu[cur] == cur)
return cur;
return dsu[cur] = par(dsu[cur]);
};
alledges = vector<int>(M);
iota(alledges.begin(), alledges.end(), 0);
sort(alledges.begin(), alledges.end(),
[&](int a, int b) { return W[a] < W[b]; });
vector<vector<int>> adj(N);
vector<pair<int, int>> vpii(N);
for (int i = 0; i < N; i++)
vpii[i] = {i, i};
lin = vector<bool>(N, 1);
for (auto in : alledges) {
adj.push_back({});
dsu.push_back(dsu.size());
vpii.push_back({-1, -1});
lin.push_back(0);
if (par(U[in]) != par(V[in])) {
adj.back().push_back(par(U[in])), adj.back().push_back(par(V[in]));
if (!lin[par(U[in])] || !lin[par(V[in])])
lin.back() = 0;
else if ((U[in] == vpii[par(U[in])].first ||
U[in] == vpii[par(U[in])].second) &&
(V[in] == vpii[par(V[in])].first ||
V[in] == vpii[par(V[in])].second)) {
lin.back() = 1;
multiset<int> si;
si.insert(vpii[par(U[in])].first);
si.insert(vpii[par(U[in])].second);
si.insert(vpii[par(V[in])].first);
si.insert(vpii[par(V[in])].second);
si.erase(si.find(U[in]));
si.erase(si.find(V[in]));
vpii.back() = {*si.begin(), *si.rbegin()};
} else {
lin.back() = 0;
}
} else {
adj.back().push_back(par(U[in]));
lin.back() = 0;
}
dsu[par(U[in])] = dsu.back(), dsu[par(V[in])] = dsu.back();
}
bin = vector<vector<int>>(logn, vector<int>(N + M));
depvi = vector<int>(N + M);
function<void(int, int, int)> fvii = [&](int cur, int par, int dep) {
bin[0][cur] = par;
depvi[cur] = dep;
for (auto a : adj[cur])
fvii(a, cur, dep + 1);
};
fvii(N + M - 1, N + M - 1, 0);
for (int i = 1; i < logn; i++)
for (int j = 0; j < N + M; j++)
bin[i][j] = bin[i - 1][bin[i - 1][j]];
}
int getMinimumFuelCapacity(int X, int Y) {
if (lin.back() == 1)
return -1;
int tmpx = X, tmpy = Y;
if (depvi[tmpx] > depvi[tmpy])
swap(tmpx, tmpy);
for (int i = logn - 1; i >= 0; i--) {
if ((depvi[tmpy] - depvi[tmpx]) & (1 << i)) {
tmpy = bin[i][tmpy];
}
}
for (int i = logn - 1; i >= 0; i--) {
if (bin[i][tmpx] != bin[i][tmpy])
tmpx = bin[i][tmpx], tmpy = bin[i][tmpy];
}
if (tmpx != tmpy) {
tmpx = bin[0][tmpx], tmpy = bin[0][tmpy];
}
int lca = tmpx;
if (!lin[lca])
return w[alledges[lca - n]];
for (int i = logn - 1; i >= 0; i--) {
if (lin[bin[i][lca]]) {
lca = bin[i][lca];
}
}
lca = bin[0][lca];
return w[alledges[lca - n]];
}
