#include <bits/stdc++.h>
#define pb push_back
using namespace std;
int _n, _m;
int timer;
vector<int> tin, tout, cost;
vector<vector<pair<int, int>>> edge;
vector<vector<int>> ancestor, max_weight;
void dfs (int v, int par) {
tin[v] = timer++;
for (auto [child, w] : edge[v]) {
if (child == par) continue;
ancestor[v][0] = par;
max_weight[child][0] = w;
dfs(child, v);
}
tout[v] = timer++;
}
bool is_ancestor (int child, int p) {
return tin[child] <= tin[p] && tout[child] >= tout[p];
}
int LCA (int u, int v) {
if (is_ancestor(u, v)) return u;
if (is_ancestor(v, u)) return v;
for (int i = 19; i >= 0; i --) {
if (!is_ancestor(ancestor[u][i], v)) u = ancestor[u][i];
}
return ancestor[u][0];
}
int MAX_W (int child, int lca) {
if (child == lca) {return 0;}
int m = 0, i = 19;
while (ancestor[child][0] != lca) {
if (!is_ancestor(child, ancestor[child][i])) {
m = max(m, max_weight[child][i]);
child = ancestor[child][i];
}
i--;
}
return m;
}
void preprocess (int v) {
}
void preprocess_cost (int v, int p) {
for (auto [child, w] : edge[v]) {
if (child == p) continue;
preprocess_cost (child, v);
}
if (edge[v].size() >= 3) {
int min1=1e9, min2=1e9, min3=1e9;
for (auto [child, w] : edge[v]) {
if (w <= min1) {
min3 = min2;
min2 = min1;
min1 = w;
}
else if (w <= min2) {
min3 = min2;
min2 = w;
}
else if (w <= min3) {
min3 = w;
}
}
cost[v] = min3;
}
for (auto [child, w] : edge[v]) {
if (child == p) continue;
cost[v] = min(cost[v], max(cost[child], w));
}
}
void preprocess_cost2 (int v, int p) {
for (auto [child, w] : edge[v]) {
if (child == p) continue;
cost[child] = min(cost[child], max(cost[v], w));
preprocess_cost2 (child, v);
}
}
void init (int n, int m, vector<int> u, vector<int> v, vector<int> w) {
edge.resize(n);
for (int i = 0; i < m; i ++) {
edge[u[i]].pb({v[i], w[i]});
edge[v[i]].pb({u[i], w[i]});
}
_n = n; _m = m;
timer = 0;
ancestor[0][0] = 0;
max_weight[0][0] = 0;
tin.resize(_n); tout.resize(_n);
ancestor.resize(n, vector<int>(20));
max_weight.resize(n, vector<int>(20));
dfs(0, -1);
for (int i = 1; i <= 19; i ++) {
for (int j = 0; j < n; j ++) {
ancestor[j][i] = ancestor[ancestor[j][i-1]][i-1];
max_weight[j][i] = max(max_weight[j][i-1], max_weight[ancestor[j][i-1]][i-1]);
}
}
cost.resize(_n, 1e9);
preprocess_cost(0, -1);
preprocess_cost2(0, -1);
}
int getMinimumFuelCapacity(int x, int y) {
int lca = LCA(x, y);
int path_max_w = max(MAX_W(x, lca), MAX_W(y, lca));
int extra_cost = cost[x];
int ans = max(extra_cost, path_max_w);
if (ans == 1e9) ans = -1;
return ans;
}
