#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100'000 + 12;
vector<pair<int, int>> g[maxn], t[maxn], e[maxn];
int up[20][maxn], mx[20][maxn], mn[20][maxn];
int p[maxn], d[maxn], dist[maxn];
int n, m;
int get(int x) {
if(p[x] == x) return x;
return p[x] = get(p[x]);
}
void dfs(int v, int p, int w) {
up[0][v] = p;
mx[0][v] = w;
for(auto [to, c] : t[v]) {
if(to == p) {
continue;
}
e[v].push_back({to, c});
}
mn[0][v] = 2e9;
if(e[v].size() >= 2) {
mn[0][v] = e[v][1].second;
}
for(int i = 1; i < 20; i++) {
up[i][v] = up[i - 1][up[i - 1][v]];
mx[i][v] = max(mx[i - 1][v], mx[i - 1][up[i - 1][v]]);
mn[i][v] = min(mn[i - 1][v], mn[i - 1][up[i - 1][v]]);
}
for(auto [to, c] : g[v]) {
if(to != p) {
d[to] = d[v] + 1;
dfs(to, v, c);
}
}
}
int get(int u, int v) {
int ansMx = 0, ansMn = min(dist[u], dist[v]);
if(d[u] < d[v]) {
swap(u, v);
}
for(int i = 19; i >= 0; i--) {
if(d[u] - d[v] >= (1 << i)) {
ansMx = max(ansMx, mx[i][u]);
ansMn = min(ansMn, mn[i][u]);
u = up[i][u];
}
}
if(u == v) {
return max(ansMx, ansMn);
}
for(int i = 19; i >= 0; i--) {
if(up[i][u] != up[i][v]) {
ansMx = max({ansMx, mx[i][u], mx[i][v]});
ansMn = min({ansMn, mn[i][u], mn[i][v]});
u = up[i][u], v = up[i][v];
}
}
ansMx = max({ansMx, mx[0][u], mx[0][v]});
u = up[0][u];
if(t[u].size() > 2) {
ansMn = min(ansMn, t[u][2].second);
}
return max(ansMx, ansMn);
}
void init(int N, int M,
std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n = N, m = M;
vector<array<int, 3>> edge;
for(int i = 0; i < m; i++) {
t[U[i]].push_back({V[i], W[i]});
t[V[i]].push_back({U[i], W[i]});
edge.push_back({U[i], V[i], W[i]});
}
for(int i = 0; i < n; i++) {
p[i] = i;
dist[i] = 2e9;
sort(t[i].begin(), t[i].end(), [](pair<int, int> x, pair<int, int> y) {
return x.second < y.second;
});
if(t[i].size() >= 3) {
dist[i] = t[i][2].second;
}
}
sort(edge.begin(), edge.end(), [](array<int, 3> x, array<int, 3> y) {
return x[2] < y[2];
});
for(auto [u, v, w] : edge) {
if(get(u) != get(v)) {
p[get(u)] = get(v);
g[v].push_back({u, w});
g[u].push_back({v, w});
}
else {
dist[u] = min(dist[u], w);
}
}
set<pair<int, int>> s;
for(int i = 0; i < n; i++) {
s.insert({dist[i], i});
}
while(!s.empty()) {
int v = s.begin() -> second;
s.erase(s.begin());
for(auto [to, w] : t[v]) {
if(max(dist[v], w) < dist[to]) {
s.erase({dist[to], to});
dist[to] = max(dist[v], w);
s.insert({dist[to], to});
}
}
}
dfs(0, 0, 0);
}
int getMinimumFuelCapacity(int X, int Y) {
if(get(X, Y) > 1e9) {
return -1;
}
return get(X, Y);
}
