#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define forn(i, n) for (i = 0; i < n; i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define fr first
#define se second
using namespace std;
const int MAXN = 1e5 + 1;
const int LOG = 20;
const ll INF = LLONG_MAX;
vector<pair<ll, ll>> grafo[MAXN], grafo2[MAXN];
ll up[MAXN][LOG], miA[MAXN][LOG], disUp[MAXN][LOG], mi2D[MAXN], mi2DU[MAXN], prof[MAXN];
void dfs(ll nod, ll pad)
{
up[nod][0] = pad;
ll cant = 0;
for (auto k : grafo[nod])
{
cant++;
if (cant == 3)
{
miA[nod][0] = k.fr;
break;
}
}
for (ll i = 1; i < LOG; i++)
{
up[nod][i] = up[up[nod][i - 1]][i - 1];
miA[nod][i] = min(miA[nod][i - 1], miA[up[nod][i - 1]][i - 1]);
disUp[nod][i] = max(disUp[nod][i - 1], disUp[up[nod][i - 1]][i - 1]);
}
ll act = 0;
cant = 0;
for (auto k : grafo[nod])
{
if (k.se == pad)
continue;
prof[k.se] = prof[nod] + 1;
cant++;
act = max(act, k.fr);
if (cant == 2)
mi2D[nod] = min(mi2D[nod], act);
disUp[k.se][0] = k.fr;
dfs(k.se, nod);
mi2D[nod] = min(mi2D[nod], max(mi2D[k.se], k.fr));
}
}
void dfs2(ll nod, ll pad, ll pMiD2)
{
mi2DU[nod]=pMiD2;
for(auto k:grafo[nod])
{
if(k.se==pad)
continue;
ll cant=0, act=0, m2D=INF;
for(auto l:grafo[nod])
{
if(l.se==k.se)
continue;
cant++;
act=max(act,l.fr);
if(cant==2)
{
m2D=act;
break;
}
}
for(auto l:grafo2[nod])
{
if(l.se==k.se||l.se==pad)
continue;
m2D=min(m2D,mi2D[l.se]);
break;
}
dfs2(k.se,nod,max(k.fr,min(m2D,mi2DU[nod])));
}
}
ll n, m, xZ, yZ;
void init(int N, int M,
std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
n = N;
m = M;
if (M > N - 1)
return;
ll i, j;
for (i = 0; i < MAXN; i++)
{
mi2D[i] = INF;
mi2DU[i] = INF;
for (j = 0; j < LOG; j++)
{
miA[i][j] = INF;
}
}
for (i = 0; i < M; i++)
{
grafo[U[i]].pb({W[i], V[i]});
grafo[V[i]].pb({W[i], U[i]});
}
for (i = 0; i < N; i++)
sort(all(grafo[i]));
dfs(0, 0);
for (i = 0; i < M; i++)
{
grafo2[U[i]].pb({mi2D[V[i]], V[i]});
grafo2[V[i]].pb({mi2D[U[i]], U[i]});
}
for (i = 0; i < N; i++)
sort(all(grafo2[i]));
dfs2(0,0,INF);
}
ll k_ans(ll a, ll d)
{
ll i;
for (i = 0; i < LOG; i++)
if ((1 << i) & d)
a = up[a][i];
return a;
}
ll lca(ll a, ll b)
{
if (prof[b] > prof[a])
swap(a, b);
if (a == b)
return a;
ll i, d = prof[a] - prof[b];
xZ = k_ans(a, d - 1);
yZ = b;
a = k_ans(a, d);
if (a == b)
return a;
for (i = LOG - 1; i >= 0; i--)
{
if (up[a][i] != up[b][i])
{
a = up[a][i];
b = up[b][i];
}
}
xZ = a;
yZ = b;
return up[a][0];
}
ll dist(ll a, ll b)
{
if (a == b)
return 0;
ll d = prof[a] - prof[b], i, act = 0;
for (i = 0; i < LOG; i++)
{
if ((1 << i) & d)
{
act = max(act, disUp[a][i]);
a = up[a][i];
}
}
return act;
}
ll getMiA(ll a, ll b)
{
if (a == b)
return INF;
a = up[a][0];
ll d = prof[a] - prof[b], i, act = INF;
for (i = 0; i < LOG; i++)
{
if ((1 << i) & d)
{
act = min(act, miA[a][i]);
a = up[a][i];
}
}
act=min(act,miA[a][0]);
return act;
}
int getMinimumFuelCapacity(int X, int Y)
{
if (m > n - 1 || X == Y)
return -1;
ll Z = lca(X, Y), act = max(dist(X, Z), dist(Y, Z)), ag;
ag = min(getMiA(X, Z), getMiA(Y, Z));
if (ag <= act)
return act;
if (X != Z)
ag = min(ag, mi2D[X]);
if (Y != Z)
ag = min(ag, mi2D[Y]);
if (ag <= act)
return act;
if (Y == Z)
swap(X, Y);
if (X == Z)
{
ll cal = 0, cant = 0;
for (auto k : grafo[X])
{
if (k.se == xZ || k.se == yZ)
continue;
cant++;
cal = max(cal, k.fr);
if (cant == 2)
break;
}
if (cant == 2)
ag = min(ag, cal);
if (ag <= act)
return act;
for (auto k : grafo2[X])
{
if (k.se == xZ || k.se == yZ || k.se==up[X][0])
continue;
ag = min(ag, k.fr);
break;
}
if (ag <= act)
return act;
ag=min(ag,mi2DU[X]);
if (ag <= act)
return act;
}
act=max(ag,act);
if(act==INF)
return -1;
return act;
}
