#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 310000;
const int LOGN = 20;
int n, m, p[N], s[N], es[N][2], t[N], vw[N], depth[N], jmp[N][LOGN];
bool good[N], path[N];
vector<array<int, 3>> edge;
vector<int> g[N];
void init_dsu() {
for (int i = 1; i <= n; i++) {
path[i] = true;
es[i][0] = es[i][1] = p[i] = t[i] = i;
}
}
int getp(int x) {
return x == p[x] ? x : p[x] = getp(p[x]);
}
void unite(int u, int v, int w, int k) {
int a = getp(u);
int b = getp(v);
if (a == b) {
g[k].push_back(t[a]);
path[a] = false;
} else {
g[k].push_back(t[a]);
g[k].push_back(t[b]);
if (s[a] < s[b]) swap(a, b);
s[a] += s[b];
p[b] = a;
if (!path[a] || !path[b])
path[a] = false;
else {
if ((u == es[a][0] || u == es[a][1]) && (v == es[b][0] || v == es[b][1])) {
int x = es[a][0] + es[a][1] - u;
int y = es[b][0] + es[b][1] - v;
es[a][0] = x;
es[a][1] = y;
} else path[a] = false;
}
}
good[k] = !path[a];
vw[k] = w;
t[a] = k;
}
void dfs(int v, int p = -1) {
depth[v] = (p == -1 ? 0 : depth[p] + 1);
jmp[v][0] = (p == -1 ? v : p);
for (int k = 1; k < LOGN; k++)
jmp[v][k] = jmp[jmp[v][k - 1]][k - 1];
for (int u : g[v])
dfs(u, v);
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
n = N;
m = M;
for (int i = 0; i < m; i++)
edge.push_back({W[i], U[i] + 1, V[i] + 1});
sort(begin(edge), end(edge));
init_dsu();
for (int i = 0; i < m; i++)
unite(edge[i][1], edge[i][2], edge[i][0], n + 1 + i);
dfs(n + m);
}
int lca(int a, int b) {
if (depth[a] < depth[b])
swap(a, b);
for (int k = LOGN - 1; k >= 0; k--)
if (depth[a] - (1 << k) >= depth[b])
a = jmp[a][k];
if (a == b) return a;
for (int k = LOGN - 1; k >= 0; k--)
if (jmp[a][k] != jmp[b][k]) {
a = jmp[a][k];
b = jmp[b][k];
}
return jmp[a][0];
}
int getMinimumFuelCapacity(int X, int Y) {
X++; Y++;
int L = lca(X, Y);
if (good[L]) return vw[L];
for (int k = LOGN - 1; k >= 0; k--)
if (!good[jmp[L][k]])
L = jmp[L][k];
L = jmp[L][0];
if (good[L]) return vw[L];
return -1;
}
