#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
const int N = 1<<17;
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 moveUp(int v, int d, int t, 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;
}
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], moveUp(u, hei[u] - hei[i], 0));
// if (mn == 2){
// cout<<u<<" "<<i<<" "<<p<<" eendndkdn "<<hei[u] - hei[i]<<" "<<Mx[u][1]<<" "<<moveUp(u, hei[u] - hei[i], 0)<<endl;
// }
ins[i].push_back(mn);
ers[u].push_back(mn);
}
else if (seen[i] != 1){
// cout<<u<<" --> "<<i<<endl;
dfs1(i, u, id2);
}
}
}
multiset<int> ms;
void dfs2(int u, int p, int id){
seen[u] = 2;
for (int i : ins[u])
ms.insert(i);
if (ms.size() > 0)
MinCycle[u] = *ms.begin();
else
MinCycle[u] = inf;
for (auto [i, id2] : nei[u]){
if (id2 != id and seen[i] != 2)
dfs2(i, u, id2);
}
for (int i : ers[u])
ms.erase(ms.find(i));
}
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);
dfs2(1, 0, N - 1);
for (int i=0;i<=n;i++){
nei[i].clear(), parent[i] = i;
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);
}
int getMinimumFuelCapacity(int u, int v){
u++, v++;
int AnsCycle = min(MinCycle[u], MinCycle[v]), EndPoint;
int a = u, b = v, minEx = inf, maxOnPath = 0;
if (hei[a] > hei[b])
swap(a, b);
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]){
maxOnPath = max(maxOnPath, Mx[b][i]);
minEx = min(minEx, Mn[b][i]);
// cout<<b<<" --> "<<Par[b][i]<<" "<<i<<endl;
b = Par[b][i];
}
}
maxOnPath = max(maxOnPath, Mx[b][0]);
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]);
// cout<<u<<" "<<v<<" "<<a<<" "<<b<<endl;
// cout<<EndPoint<<endl;
// cout<<minEx<<endl;
// cout<<AnsCycle<<endl;
}
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]){
minEx = min(minEx, Mn[b][0]);
b = Par[b][0];
}
for (int i=16;i>=0;i--){
if (Par[a][i] == Par[b][i])
continue;
maxOnPath = max(maxOnPath, max(Mx[a][i], Mx[b][i]));
minEx = min(minEx, min(Mn[a][i], Mn[b][i]));
a = Par[a][i], b = Par[b][i];
}
int lca = Par[a][0];
// cout<<u<<" "<<v<<" "<<a<<" "<<b<<endl;
// cout<<"d0"<<endl;
weiNei[lca].erase(weiNei[lca].find(Mx[a][0]));
// cout<<"d1"<<endl;
weiNei[lca].erase(weiNei[lca].find(Mx[b][0]));
// cout<<"d2"<<endl;
minEx = min(minEx, *weiNei[lca].begin());
// cout<<"d3"<<endl;
// return 0;
weiNei[lca].insert(Mx[a][0]);
weiNei[lca].insert(Mx[b][0]);
maxOnPath = max(maxOnPath, max(Mx[a][0], Mx[b][0]));
}
int finalAns = max(maxOnPath, min(minEx, min(EndPoint, AnsCycle)));
if (finalAns == inf)
finalAns = -1;
// cout<<"done again ////////////////////////////////////////////////////////////////////////////////////////////////"<<endl;
return finalAns;
}
