#include "swap.h"
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define rep2(i, s, n) for(ll i = ll(s); i < ll(n); i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define pb push_back
#define eb emplace_back
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;
template<class T>
bool chmin(T &a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template<class T>
bool chmax(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
const int inf = 1001001001;
class unionfind {
int n;
public:
vi par, rank;
unionfind(int n) : n(n), par(n, -1), rank(n, 0) {}
int root(int x) {
if (par[x] < 0) return x;
return par[x] = root(par[x]);
}
bool same(int x, int y) {
return root(x) == root(y);
}
bool merge(int x, int y) {
x = root(x), y = root(y);
if (x == y) return false;
if (rank[x] == rank[y]) rank[x]++;
par[x] += par[y];
par[y] = x;
return true;
}
};
namespace {
struct node {
int mx;
bool is_path;
int x, y;
node(int mx, bool is_path = false, int x = 0, int y = 0)
: mx(mx), is_path(is_path), x(x), y(y) {}
};
vector<node> nodes;
vvi G;
int sz;
vvi par;
vi dep;
int lca(int u, int v) {
if (dep[u] > dep[v]) swap(u, v);
if (dep[u] < dep[v]) {
int dis = dep[v] - dep[u];
rep(k, 30) if (dis >> k & 1) v = par[k][v];
}
assert(dep[u] == dep[v]);
if (u == v) return u;
for (int k = 29; k >= 0; k--) {
if (par[k][u] == par[k][v]) continue;
u = par[k][u];
v = par[k][v];
}
assert(u != v and par[0][u] == par[0][v]);
return par[0][u];
}
}
void dfs(int u, int p, int d) {
par[0][u] = p;
dep[u] = d;
for (int v : G[u]) {
if (v == p) continue;
dfs(v, u, d + 1);
}
}
void init(int n, int m, vi u, vi v, vi w) {
vi ord(m);
iota(all(ord), 0);
sort(all(ord), [&](int i, int j) { return w[i] < w[j]; });
unionfind uf(n);
map<int, int> mp;
rep(i, n) {
nodes.eb(0, true, i, i);
mp[i] = i;
}
G.resize(n + m + 10);
for (int i : ord) {
int a = u[i], b = v[i];
if (uf.same(a, b)) {
int r = uf.root(a);
int now = mp[r];
if (!nodes[now].is_path) continue;
int nx = nodes.size();
G[now].pb(nx);
G[nx].pb(now);
nodes.eb(w[i]);
mp[r] = nx;
} else {
int ra = uf.root(a), rb = uf.root(b);
if (uf.rank[ra] < uf.rank[rb]) {
swap(a, b);
swap(ra, rb);
}
uf.merge(ra, rb);
int na = mp[ra], nb = mp[rb];
int nx = nodes.size();
G[na].pb(nx);
G[nb].pb(nx);
G[nx].pb(na);
G[nx].pb(nb);
if (!nodes[na].is_path or !nodes[nb].is_path) {
nodes.eb(w[i]);
} else {
int nx_x = -1, nx_y = -1;
if (nodes[na].x == a) nx_x = nodes[na].y;
else if (nodes[na].y == a) nx_x = nodes[na].x;
if (nodes[nb].x == b) nx_y = nodes[nb].y;
else if (nodes[nb].y == b) nx_y = nodes[nb].x;
if (nx_x == -1 or nx_y == -1) {
nodes.eb(w[i]);
} else {
nodes.eb(w[i], true, nx_x, nx_y);
}
}
mp.erase(rb);
mp[ra] = nx;
}
}
assert(mp.size() == 1);
sz = nodes.size();
par.resize(30);
rep(k, 30) par[k].resize(sz);
dep.resize(sz);
dfs(sz - 1, -1, 0);
rep(k, 29) rep(i, sz) {
if (par[k][i] < 0) par[k + 1][i] = -1;
else par[k + 1][i] = par[k][par[k][i]];
}
}
int getMinimumFuelCapacity(int x, int y) {
int l = lca(x, y);
if (!nodes[l].is_path) return nodes[l].mx;
if (nodes[sz - 1].is_path) return -1;
for (int k = 29; k >= 0; k--) {
if (par[k][l] < 0) continue;
if (!nodes[par[k][l]].is_path) continue;
l = par[k][l];
}
assert(nodes[l].is_path);
l = par[0][l];
assert(!nodes[l].is_path);
return nodes[l].mx;
}
