#include "swap.h"
#include <bits/stdc++.h>
#define maxn 300005
using namespace std;
#define fi first
#define se second
using ii = pair<int, int>;
int pos[maxn], val[maxn], id = 0;
ii f[20][maxn+maxn];
int LCA(int u, int v) {
u = pos[u]; v = pos[v];
if (u > v) swap(u, v);
int k = __lg(v-u+1);
return min(f[k][u], f[k][v-(1<<k)+1]).se;
}
int LCP(int u, int v) {
if (u > v) swap(u, v);
int k = __lg(v-u+1);
return min(f[k][u], f[k][v-(1<<k)+1]).se;
}
set<int> nho;
void init(int N, int M,
vector<int> U, vector<int> V, vector<int> W) {
for (int i = 0; i < M; i++) {++U[i]; ++V[i];}
struct edge {
int u, v, l;
edge() {}
edge(int _u, int _v, int _l) : u(_u), v(_v), l(_l) {}
bool operator < (const edge &other) const {
return l < other.l;
}
} edges[M+1];
for (int i = 0; i < M; i++) edges[i+1] = edge(U[i], V[i], W[i]);
sort(edges + 1, edges + M + 1);
int lt[N+1], deg[N+1], flag[N+1], maxdeg[N+1];
for (int i = 1; i <= N; i++) {
lt[i] = i;
deg[i] = flag[i] = maxdeg[i] = 0;
}
function<int(int)> found_set = [&](int v) {
return lt[v] == v ? v : lt[v] = found_set(lt[v]);
};
function<void(int, int)> onion_set = [&](int u, int v) {
int a = ++deg[u], b = ++deg[v];
u = found_set(u); v = found_set(v);
if (u == v) {
flag[u] = 1;
maxdeg[u] = max({maxdeg[u], a, b});
return;
}
lt[u] = v;
flag[v] |= flag[u];
maxdeg[v] = max({maxdeg[v], a, b});
};
int par[N+M+1], good[N+M+1];
fill(good + 1, good + N + M + 1, 0);
iota(par + 1, par + N + M + 1, 1);
function<int(int)> find_set = [&](int v) {return par[v] == v ? v : par[v] = find_set(par[v]);};
int root = N;
vector<int> adj[N+M+1];
for (int i = 1; i <= M; i++) {
auto [u, v, l] = edges[i];
onion_set(u, v);
int w = found_set(u);
++root;
if (flag[w] || maxdeg[w] >= 3) good[root] = 1;
u = find_set(u); v = find_set(v);
val[root] = l;
adj[root].emplace_back(u);
if (u != v) adj[root].emplace_back(v);
par[u] = par[v] = root;
}
int d[N+M+1];
function<void(int)> dfs = [&](int u) {
f[0][++id] = {d[u], u};
pos[u] = id;
if (good[u]) nho.insert(id);
for (int v : adj[u]) {
d[v] = d[u] + 1;
dfs(v);
f[0][++id] = {d[u], u};
}
};
d[root] = 0;
dfs(root);
for (int i = 1; (1<<i) <= id; i++) for (int j = 1; j + (1<<i) - 1 <= id; j++) f[i][j] = min(f[i-1][j], f[i-1][j+(1<<(i-1))]);
}
int getMinimumFuelCapacity(int X, int Y) {
++X; ++Y;
if (nho.size() == 0) return -1;
int p = LCA(X, Y);
int u = pos[p];
auto it = nho.lower_bound(u);
int ans = INT_MAX;
if (it != nho.end()) {
ans = min(ans, val[LCP(u, *it)]);
}
if (it != nho.begin()) {
--it;
ans = min(ans, val[LCP(u, *it)]);
}
return ans;
}
