#include "swap.h"
#include <bits/stdc++.h>
constexpr int N = 3e5 + 5;
int n, m;
int up[N][20], f[N], ans[N], tin[N], tout[N];
std::vector<int> e[N], to[N];
struct desu{
std::vector<int> p;
desu(int n){
p.assign(n, 0);
iota(p.begin(), p.end(), 0);
}
int leader(int u){
return (u == p[u] ? u : p[u] = leader(p[u]));
}
void merge(int u, int v){
u = leader(u);
v = leader(v);
if (u == v) return;
p[v] = u;
}
bool same(int u, int v){
return leader(u) == leader(v);
}
}d(N);
int timer = 0;
void dfs(int u, int p){
tin[u] = timer++;
up[u][0] = p;
for (int i = 1; i < 20; i++) up[u][i] = up[up[u][i - 1]][i - 1];
for (auto v : to[u]) {
dfs(v, u);
}
tout[u] = timer;
}
bool is(int u, int v) { return tin[u] <= tin[v] && tout[u] >= tout[v]; }
int lca(int u, int v){
if (is(u, v)) return u;
if (is(v, u)) return v;
for (int i = 19; i >= 0; i--) {
if (!is(up[u][i], v)) u = up[u][i];
}
return up[u][0];
}
bool answer;
void init(int n, int m, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
::n = n;
::m = m;
std::vector<std::tuple<int, int, int>> edges;
for (int i = 0; i < m; i++) {
edges.emplace_back(W[i], U[i], V[i]);
}
sort(edges.begin(), edges.end());
for (auto [w, u, v] : edges) {
int nd = n++;
ans[nd] = w;
e[u].push_back(v);
e[v].push_back(u);
if (d.same(u, v)) {
f[nd] = true;
to[nd].push_back(d.leader(u));
d.merge(nd, u);
} else {
to[nd].push_back(d.leader(u));
to[nd].push_back(d.leader(v));
f[nd] = f[d.leader(u)] | f[d.leader(v)] | (e[u].size() > 2 || e[v].size() > 2);
d.merge(nd, u);
d.merge(nd, v);
}
}
assert(n == ::n + m);
dfs(n - 1, n - 1);
if (f[n - 1]) answer = true;
}
int getMinimumFuelCapacity(int X, int Y) {
// if (!answer) return -1;
int l = lca(X, Y);
if (f[l]) return ans[l];
for (int i = 19; i >= 0; i--)
if (!f[up[l][i]]) l = up[l][i];
l = up[l][0];
if(f[l]) return ans[l];
return -1;
}
