#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1<<18;
vector<pair<int,int>> nei[N], nei2[N], Ed;
int Edge[N], Par[N],hei[N], MinTrg[N], seen[N], Sz[N], inf = 1e9 + 7;
void dfs1(int u){
for (auto [i, w] : nei2[u]){
dfs1(i);
MinTrg[u] = min(MinTrg[u], max(MinTrg[i], w));
}
}
void dfs2(int u, int p = 0){
hei[u] = hei[p] + 1;
for (auto [i, w] : nei2[u]){
MinTrg[i] = min(MinTrg[i], max(MinTrg[u], w));
dfs2(i, u);
}
}
int root(int v){
while (Par[v])
v = Par[v];
return v;
}
void init(int n, int m, vector<int> u, vector<int> v, vector<int> w){
for (int i=0;i<m;i++){
u[i]++, v[i]++;
nei[u[i]].push_back({v[i], w[i]});
nei[v[i]].push_back({u[i], w[i]});
Ed.push_back({w[i], i});
}
for (int u=1;u<=n;u++){
int m1 = inf, m2 = inf, m3 = inf;
for (auto [i, w] : nei[u]){
if (w < m1)
m3 = m2, m2 = m1, m1 = w;
else if (w < m2)
m3 = m2, m2 = w;
else
m3 = min(m3, w);
}
MinTrg[u] = m3, Sz[u] = 1;
}
sort(begin(Ed), end(Ed));
for (auto [c, i] : Ed){
int A = root(u[i]), B = root(v[i]);
if (A == B){
MinTrg[A] = min(MinTrg[A], c);
continue;
}
if (Sz[A] < Sz[B])
swap(A, B);
Par[B] = A, Sz[A] += Sz[B], Edge[B] = c;
nei2[A].push_back({B, c});
}
dfs1(root(1));
dfs2(root(1));
}
int getMinimumFuelCapacity(int u, int v){
u++, v++;
int ans = min(MinTrg[u], MinTrg[v]);
if (hei[u] > hei[v])
swap(u, v);
while (hei[v] > hei[u])
ans = max(ans, Edge[v]), v = Par[v];
while (u != v)
ans = max(ans, max(Edge[u], Edge[v])), v = Par[v], u = Par[u];
if (ans == inf)
ans = -1;
return ans;
}
