#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
int n, m;
const int N = (int)2e5 + 5;
vector<pair<int, int>> adj[N];
int mx[19][N], dp[19][N], dep[N], dis[N];
int kth(int v, int k) {
for (int j = 0; j < 19; j++) {
if ((1 << j) & k) {
v = dp[j][v];
}
}
return v;
}
int val(int v, int k) {
int ret = 0;
for (int j = 0; j < 19; j++) {
if ((1 << j) & k) {
ret = max(ret, mx[j][v]);
v = dp[j][v];
}
}
return ret;
}
int Lca(int u, int v) {
if (dep[u] > dep[v]) swap(u, v);
v = kth(v, dep[v] - dep[u]);
for (int j = 18; j >= 0; j--) {
if (dp[j][v] != dp[j][u]) {
v = dp[j][v], u = dp[j][u];
}
}
return (u == v ? u : dp[0][u]);
}
int path(int u, int v) {
int lca = Lca(u, v);
return max(val(u, dep[u] - dep[lca]), val(v, dep[v] - dep[lca]));
}
void dfs(int v, int par) {
dep[v] = dep[par] + 1;
for (auto [u, w]: adj[v]) {
if (u == par) continue;
mx[0][u] = w;
dp[0][u] = v;
for (int j = 1; j < 19; j++) {
mx[j][u] = max(mx[j - 1][u], mx[j - 1][dp[j - 1][u]]);
dp[j][u] = dp[j - 1][dp[j - 1][u]];
}
dfs(u, v);
}
}
void init(int N2, int M, vector<int> U, vector<int> V, vector<int> W) {
n = N2, m = M;
for (int i = 0; i < m; i++) {
auto [u, v, w] = make_tuple(U[i] + 1, V[i] + 1, W[i]);
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
for (int i = 1; i <= n; i++) {
sort(adj[i].begin(), adj[i].end(), [&](pair<int, int> a, pair<int, int> b) {
return a.second < b.second;
});
}
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> se;
for (int i = 1; i <= n; i++) {
if ((int)adj[i].size() > 2) {
dis[i] = adj[i][2].second;
se.push({dis[i], i});
} else dis[i] = INT_MAX;
}
while (!se.empty()) {
auto [ds, v] = se.top();
se.pop();
if (ds != dis[v]) continue;
for (auto [u, w]: adj[v]) {
if (dis[u] > max(dis[v], w)) {
dis[u] = max(dis[v], w);
se.push({dis[u], u});
}
}
}
dfs(1, 0);
}
int getMinimumFuelCapacity(int X, int Y) {
auto [u, v] = make_tuple(X + 1, Y + 1);
if (dis[u] == INT_MAX) return -1;
return max(path(u, v), min(dis[u], dis[v]));
}
