#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
const int N = 1<<18;
vector<pair<int, int>> nei[N];
vector<int> ins[N], ers[N];
multiset<int> weiNei[N];
int Par[N][20], parent[N], hei[N], Mn[N][20], Mx[N][20], seen[N], wei[N], MinCycle[N], inf = 1e9 + 7;
int moveUpMx(int v, int d, int Ans = 0){
for (int i=0;i<17;i++){
if ((1<<i) & d)
Ans = max(Ans, Mx[v][i]), v = Par[v][i];
}
return Ans;
}
int moveUpMn(int v, int d, int Ans = inf){
for (int i=0;i<17;i++){
if ((1<<i) & d)
Ans = min(Ans, Mn[v][i]), v = Par[v][i];
}
return Ans;
}
void dfs1(int u, int p, int id){
seen[u] = 1;
hei[u] = hei[p] + 1;
Par[u][0] = p;
Mx[u][0] = wei[id];
for (int i=0;i<17;i++){
Par[u][i+1] = Par[Par[u][i]][i];
Mx[u][i+1] = max(Mx[u][i], Mx[Par[u][i]][i]);
}
for (auto [i, id2] : nei[u]){
if (id2 == id)
continue;
if (seen[i] == 1 and hei[i] < hei[u]){
int mn = max(wei[id2], moveUpMx(u, hei[u] - hei[i]));
MinCycle[u] = mn;
}
else if (seen[i] != 1){
dfs1(i, u, id2);
}
}
}
void dfs2(int u, int p){
for (auto [i, w] : nei[u]){
if (i == p)
continue;
dfs2(i, u);
MinCycle[u] = min(MinCycle[u], max(w, MinCycle[i]));
}
}
void dfs4(int u, int p, int mx = inf){
MinCycle[u] = min(MinCycle[u], mx);
mx = min(mx, MinCycle[u]);
for (auto [i, w] : nei[u])
if (i != p)
dfs4(i, u, max(mx, w));
}
int root(int v){
return (parent[v] == v ? v : parent[v] = root(parent[v]));
}
void dfs3(int u, int p, int edWei){
weiNei[p].erase(weiNei[p].find(edWei));
Mn[u][0] = *weiNei[p].begin();
Mx[u][0] = edWei;
hei[u] = hei[p] + 1;
Par[u][0] = p;
for (int i=0;i<17;i++){
Par[u][i+1] = Par[Par[u][i]][i];
Mx[u][i+1] = max(Mx[u][i], Mx[Par[u][i]][i]);
Mn[u][i+1] = min(Mn[u][i], Mn[Par[u][i]][i]);
}
for (auto [i, c] : nei[u]){
if (i == p)
continue;
weiNei[i].erase(weiNei[i].find(c));
dfs3(i, u, c);
weiNei[i].insert(c);
}
weiNei[p].insert(edWei);
}
void init(int n, int m, vector<int> u, vector<int> v, vector<int> w){
vector<pair<int, pair<int,int>>> Ed;
for (int i=0;i<m;i++){
wei[i] = w[i];
u[i]++, v[i]++;
weiNei[u[i]].insert(w[i]);
weiNei[v[i]].insert(w[i]);
nei[u[i]].push_back({v[i], i});
nei[v[i]].push_back({u[i], i});
Ed.push_back({w[i], {u[i], v[i]}});
}
dfs1(1, 0, N - 1);
for (int i=0;i<=n;i++){
nei[i].clear(), parent[i] = i;
if (MinCycle[i] == 0)
MinCycle[i] = inf;
weiNei[i].insert(inf);
weiNei[i].insert(inf);
}
sort(Ed.begin(), Ed.end());
for (auto [c, pr] : Ed){
int A = root(pr.first), B = root(pr.second);
if (A != B){
parent[B] = A;
nei[pr.first].push_back({pr.second, c});
nei[pr.second].push_back({pr.first, c});
// cout<<pr.first<<" "<<pr.second<<" "<<c<<endl;
}
}
dfs3(1, 0, inf);
dfs2(1, 0);
dfs4(1, 0);
}
int getMinimumFuelCapacity(int u, int v){
u++, v++;
int AnsCycle = min(MinCycle[u], MinCycle[v]), EndPoint;
if (hei[u] > hei[v])
swap(u, v);
int a = u, b = v, minEx = inf, maxOnPath = 0;
weiNei[b].erase(weiNei[b].find(Mx[b][0]));
EndPoint = *next(weiNei[b].begin());
weiNei[b].insert(Mx[b][0]);
for (int i=16;i>=0;i--){
if (hei[a] + (1<<i) < hei[b])
b = Par[b][i];
}
if (Par[b][0] == a){
weiNei[a].erase(weiNei[a].find(Mx[b][0]));
EndPoint = min(EndPoint, *next(weiNei[a].begin()));
weiNei[a].insert(Mx[b][0]);
minEx = moveUpMn(v, hei[v] - hei[b]);
maxOnPath = moveUpMx(v, hei[v] - hei[a]);
}
else{
weiNei[a].erase(weiNei[a].find(Mx[a][0]));
EndPoint = min(EndPoint, *next(weiNei[a].begin()));
weiNei[a].insert(Mx[a][0]);
if (hei[b] != hei[a])
b = Par[b][0];
for (int i=16;i>=0;i--){
if (Par[a][i] != Par[b][i])
a = Par[a][i], b = Par[b][i];
}
int lca = Par[a][0];
minEx = min(moveUpMn(u, hei[u] - hei[a]), moveUpMn(v, hei[v] - hei[b]));
maxOnPath = max(moveUpMx(u, hei[u] - hei[lca]), moveUpMx(v, hei[v] - hei[lca]));
weiNei[lca].erase(weiNei[lca].find(Mx[a][0]));
weiNei[lca].erase(weiNei[lca].find(Mx[b][0]));
minEx = min(minEx, *weiNei[lca].begin());
weiNei[lca].insert(Mx[a][0]);
weiNei[lca].insert(Mx[b][0]);
}
int finalAns = max(maxOnPath, min(minEx, min(EndPoint, AnsCycle)));
if (finalAns == inf)
finalAns = -1;
return finalAns;
}
