#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], Edg[N], Par[N], stp[N][20], Mx[N][20], hei[N], MinTrg[N], seen[N], Sz[N], inf = 1e9 + 7;
void dfs(int u, int p, int id){
seen[u] = 1;
hei[u] = hei[p] + 1;
MinTrg[u] = inf;
Mx[u][0] = Edg[id];
for (int i=0;i<17;i++){
Mx[u][i+1] = max(Mx[u][i], Mx[stp[u][i]][i]);
stp[u][i+1] = stp[stp[u][i]][i];
}
int m1 = inf, m2 = inf, m3 = inf;
for (auto [i, id2] : nei[u]){
if (Edg[id2] < m1)
m3 = m2, m2 = m1, m1 = Edg[id2];
else if (Edg[id2] < m2)
m3 = m2, m2 = Edg[id2];
else
m3 = min(m3, Edg[id2]);
if (id == id2)
continue;
if (seen[i] == 1 and hei[i] < hei[u]){
int d = hei[u] - hei[i], vr = u, wei = Edg[id2];
for (int i=0;i<17;i++){
if ((1<<i) & d)
wei = max(wei, Mx[vr][i]), vr = stp[vr][i];
}
MinTrg[i] = min(MinTrg[i], wei);
}
if (!seen[i])
dfs(i, u, id2);
}
MinTrg[u] = min(MinTrg[u], m3);
}
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=1;i<=n;i++)
Sz[i] = 1;
for (int i=0;i<m;i++){
u[i]++, v[i]++;
Edg[i] = w[i];
nei[u[i]].push_back({v[i], i});
nei[v[i]].push_back({u[i], i});
Ed.push_back({w[i], i});
}
dfs(1, 0, N-1);
sort(begin(Ed), end(Ed));
for (auto [c, i] : Ed){
int A = root(u[i]), B = root(v[i]);
if (A == B)
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;
}
