#include<bits/stdc++.h>
#define pb push_back
using namespace std;
int N, M;
int l = 19;
int timer;
vector<vector<pair<int, int>>> edge;
vector<int> tin, tout, cost;
vector<vector<int>> ancestor, max_weight;
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;
ancestor[u.first][0] = v;
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;
ancestor.resize(N, vector<int>(l+1));
max_weight.resize(N, vector<int>(l+1, 0));
dfs(root, root);
}
void preprocess2 (int cur, int pre) {
for (auto i : edge[cur]) {
if (i.first == pre) continue;
preprocess2(i.first, cur);
}
if (edge[cur].size() >= 3) {
int min1 = 1e9, min2 = 1e9, min3 = 1e9;
for (auto j : edge[cur]) {
if (j.second <= min1) {
min3 = min2;
min2 = min1;
min1 = j.first;
}
else if (j.second <= min2) {
min3 = min2;
min2 = j.first;
}
else if (j.second <= min3) {
min3 = j.first;
}
}
cost[cur] = min3;
}
else cost[cur] = 1e9;
for (auto i : edge[cur]) {
if (i.first == pre) continue;
cost[cur] = min(cost[cur], max(cost[i.first], i.second));
}
}
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);
N = n;
M = m;
preprocess(0);
preprocess2(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 ans = max(path_max_w, cost[x]);
if (ans >= 1e9) {ans = -1;}
return ans;
}
