#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(v) v.begin(), v.end()
#define endl '\n'
#define pl(var) " [" << #var << ": " << (var) << "] "
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "[" << p.first << ", " << p.second << "]"; }
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) { cout << "["; for(int i = 0; i < (int)v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";}
template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) { cin >> p.first; return cin >> p.second; }
int n, m;
// vector<int> _u, _v, w;
vector<int> dp, dep;
vector<vector<pair<int, int>>> adj;
vector<vector<int>> jumpNode, jumpMax;
const int LOG = 20;
int inf = 1e9 + 7;
void dfs(int u, int par, int wt) {
if (u != par) dep[u] = dep[par] + 1;
else dep[u] = 0;
jumpNode[u][0] = par;
if (wt != -1) jumpMax[u][0] = wt;
if (adj[u].size() >= 3) {
priority_queue<int> best;
for (auto [_, _wt] : adj[u]) best.push(-_wt);
best.pop();
best.pop();
dp[u] = -best.top();
// cout << pl(best.top()) << endl;
}
for (auto [v, _wt] : adj[u]) {
if (v == par) continue;
dfs(v, u, _wt);
}
for (auto [v, _] : adj[u]) {
if (v == par) continue;
dp[u] = min(dp[u], max(dp[v], _));
dp[v] = min(dp[v], max(dp[u], _));
}
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
// solve the tree case
// get the max on the path from u to v <- log(n)
n = N;
m = M;
assert(m == n - 1); // just the tree case
dp = vector<int>(n, inf);
// dp.resize(n);
adj.resize(n);
dep.resize(n);
jumpNode = vector<vector<int>>(n, vector<int>(LOG));
jumpMax = vector<vector<int>>(n, vector<int>(LOG));
for (int i = 0; i < m; i++) {
adj[U[i]].emplace_back(V[i], W[i]);
adj[V[i]].emplace_back(U[i], W[i]);
}
dfs(0, 0, -1);
for (int i = 1; i < LOG; i++) {
for (int j = 0; j < n; j++) {
jumpNode[j][i] = jumpNode[jumpNode[j][i - 1]][i - 1];
jumpMax[j][i] = max(jumpMax[j][i - 1], jumpMax[jumpNode[j][i - 1]][i - 1]);
}
}
// for (auto i : jumpMax) {
// cout << i << endl;
// }
}
pair<int, int> kth(int a, int k) {
int res = 0;
int pow = LOG - 1;
while (k > 0) {
if (k < (1 << pow)) pow--;
res = max(res, jumpMax[a][pow]);
a = jumpNode[a][pow];
k -= (1 << k);
}
return make_pair(a, res);
}
int get_cost(int a, int b) {
int res = 0;
if (dep[a] < dep[b]) {
swap(a, b);
}
pair<int, int> rres = kth(a, dep[a] - dep[b]);
res = rres.second;
a = rres.first;
int pow = LOG - 1;
// cout << pl(a) << pl(b) << endl;
// cout << pl(res) << endl;
if (a == b) {
return res;
}
while (pow >= 0) {
if (jumpNode[a][pow] != jumpNode[b][pow]) {
res = max({
res,
jumpMax[a][pow],
jumpMax[b][pow]
});
a = jumpNode[a][pow];
b = jumpNode[b][pow];
}
pow--;
}
assert(jumpNode[a][0] == jumpNode[b][0]);
return max({res, jumpMax[a][0], jumpMax[b][0]});
}
int getMinimumFuelCapacity(int x, int y) {
if (n == 2) return -1;
int res = max(dp[x], get_cost(x, y));
return res >= inf ? -1 : res;
}
