#include<bits/stdc++.h>
#define pb push_back
using namespace std;
int N, M;
int l;
int timer;
vector<vector<pair<int, int>>> edge;
vector<int> tin, tout;
vector<vector<int>> ancestor, max_weight;
vector<int> cost;
void dfs (int v, int p) {
tin[v] = timer++;
ancestor[v][0] = p;
for (int i = 1; i <= l; i ++) {
ancestor[v][i] = ancestor[ancestor[v][i-1]][i-1];
max_weight[v][i] = max(max_weight[v][i-1], max_weight[ancestor[v][i-1]][i-1]);
}
for (auto u : edge[v]) {
if (u.first != p) {
max_weight[u.first][0] = u.second;
dfs(u.first, v);
}
}
tout[v] = timer++;
}
bool is_ancestor(int u, int v) {
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int u, int v) {
if (is_ancestor(u, v)) return u;
if (is_ancestor(v, u)) return v;
for (int i = l; i >= 0; i --) {
if (!is_ancestor(ancestor[u][i], v)) u = ancestor[u][i];
}
return ancestor[u][0];
}
int max_w(int u, int LCA) {
if (u == LCA) {return 0;}
int i = l;
int m = 0;
while (ancestor[u][0] != LCA) {
if (!is_ancestor(ancestor[u][i], LCA)) {
m = max(m, max_weight[u][i]);
u = ancestor[u][i];
}
i --;
}
m = max(m, max_weight[u][0]);
return m;
}
void preprocess (int root) {
tin.resize(N);
tout.resize(N);
timer = 0;
l = ceil(log2(N));
ancestor.resize(N, vector<int>(l+1));
max_weight.resize(N, vector<int>(N, 0));
dfs(root, root);
}
void init (int n, int m, vector<int> u, vector<int> v, vector<int> w) {
edge.resize(n+1);
for (int i = 0; i < m; i ++) {
edge[v[i]].pb({u[i], w[i]});
edge[u[i]].pb({v[i], w[i]});
}
cost.resize(n+1, 1e9);
for (int i = 0; i < n; i ++) {
if (edge[i].size() >= 3) {
sort(edge[i].begin(), edge[i].end(), [](pair<int, int> a, pair<int, int> b){
return a.second < b.second;
});
cost[i] = edge[i][2].second;
}
}
for (int i = 0; i < m; i ++) {
int a = u[i], b = v[i], c = w[i];
cost[a] = min(cost[a], max(cost[b], c));
cost[b] = min(cost[b], max(cost[a], c));
}
N = n;
M = m;
preprocess(0);
}
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 ans = max(path_max_w, cost[x]);
if (ans >= 1e9) {ans = -1;}
return ans;
}
