#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
template <class T> bool ckmax(T &a, T b) { return a < b ? (a = b, true) : false; }
template <class T> bool ckmin(T &a, T b) { return a > b ? (a = b, true) : false; }
const int MAXN = 3e5 + 5, LG = 18;
int deg[MAXN], lab[MAXN], n, curNode, lowOk[MAXN], up[MAXN][LG + 1], dep[MAXN];
bool ok[MAXN];
vector<int> g[MAXN];
array<int, 3> e[MAXN];
int find(int u) {
return lab[u] < 0 ? u : lab[u] = find(lab[u]);
}
void join(int u, int v) {
deg[u]++;
deg[v]++;
curNode++;
if (deg[u] >= 3 || deg[v] >= 3) ok[curNode] = 1;
u = find(u); v = find(v);
if (ok[u] || ok[v] || u == v) ok[curNode] = 1;
lab[curNode] += lab[u];
if (u != v) lab[curNode] += lab[v];
lab[u] = lab[v] = curNode;
g[curNode].emplace_back(u);
if (u != v) g[curNode].emplace_back(v);
}
void dfs(int u, int p, int lst) {
if (ok[u]) lst = u;
lowOk[u] = lst;
up[u][0] = p;
for (int i = 1; i <= LG; i++) up[u][i] = up[up[u][i - 1]][i - 1];
for (int v : g[u]) {
if (v != p) {
dep[v] = dep[u] + 1;
dfs(v, u, lst);
}
}
}
int lca(int u, int v) {
if (dep[u] < dep[v]) swap(u, v);
int need = dep[u] - dep[v];
for (int i = 0; i <= LG; i++) {
if (need >> i & 1) {
u = up[u][i];
}
}
if (u == v) return u;
for (int i = LG; i >= 0; i--) {
if (up[u][i] != up[v][i]) {
u = up[u][i];
v = up[v][i];
}
}
return up[u][0];
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
for (int i = 0; i < M; i++) {
e[i] = {W[i], U[i], V[i]};
}
sort(e, e + M);
memset(lab, -1, (N + M + 5) * sizeof(int));
curNode = N - 1;
n = N;
for (int i = 0; i < M; i++) {
join(e[i][1], e[i][2]);
}
dfs(curNode, curNode, 0);
}
int getMinimumFuelCapacity(int X, int Y) {
int l = lca(X, Y);
if (lowOk[l] < n) return -1;
return e[lowOk[l] - n][0];
}
