#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10, inf = 1e9 + 100, LG = 20;
int n, m, par[N], lp[N], h[N], par2[N][LG], dp[N][LG], wei[N], h2[N];
vector<int> ver[N];
vector<pair<int, int>> adj[N];
struct EDGE {
int u, v, w;
friend bool operator<(EDGE p1, EDGE p2) {
return p1.w < p2.w;
}
};
vector<EDGE> edge;
int get_par(int u) {
return (par[u] == -1? u: get_par(par[u]));
}
void merge(int u, int v, int w) {
int uu = u, vv = v;
u = get_par(u), v = get_par(v);
if (ver[v].size() > ver[u].size())
swap(u, v);
if (u == v) {
if (lp[u] > 1e9)
for (int x: ver[u])
lp[x] = w;
return;
}
adj[uu].push_back({vv, w});
adj[vv].push_back({uu, w});
if (lp[u] <= 1e9 && lp[v] > 1e9)
for (int x: ver[v])
lp[x] = w;
if (lp[u] > 1e9 && lp[v] <= 1e9)
for (int x: ver[u])
lp[x] = w;
par[v] = u;
wei[v] = w;
for (int x: ver[v])
ver[u].push_back(x), h2[x]++;
}
void dfs(int u) {
for (pair<int, int> e: adj[u])
if (e.first != par2[u][0]) {
par2[e.first][0] = u;
h[e.first] = h[u] + 1;
dfs(e.first);
}
}
void pre() {
sort(edge.begin(), edge.end());
memset(par, -1, sizeof par);
memset(par2, -1, sizeof par2);
memset(lp, 63, sizeof lp);
for (int i = 0; i < n; i++)
ver[i].push_back(i);
for (int i = 0; i < m; i++)
merge(edge[i].u, edge[i].v, edge[i].w);
dfs(0);
for (int i = 1; i < n; i++) {
dp[i][0] = inf;
for (pair<int, int> e: adj[par2[i][0]]) {
int v = e.first, w = e.second;
if (v != i && v != par2[par2[i][0]][0]) {
dp[i][0] = w;
break;
}
}
}
for (int j = 1; j < LG; j++)
for (int i = 0; i < n; i++)
if (h[i] >= (1 << i)) {
par2[i][j] = par2[par2[i][j - 1]][j - 1];
dp[i][j] = min(dp[i][j - 1], dp[par2[i][j - 1]][j - 1]);
}
}
void init(int nn, int mm, vector<int> u, vector<int> v, vector<int> w) {
n = nn;
m = mm;
for (int i = 0; i < m; i++)
edge.push_back({u[i], v[i], w[i]});
pre();
}
int lca(int u, int v, int res = 0) {
// cout << u << ' ' << v << endl;
if (h2[u] > h2[v]) swap(u, v);
while (h2[v] > h2[u]) {
res = max(res, wei[v]);
v = par[v];
}
if (u == v) return res;
while (par[u] != par[v]) {
res = max(res, max(wei[u], wei[v]));
u = par[u], v = par[v];
}
return max(res, max(wei[u], wei[v]));
}
int lca2(int u, int v, int res = inf) {
if (h[u] > h[v]) swap(u, v);
int cnt = 0;
for (pair<int, int> e: adj[v]) {
int x = e.first, w = e.second;
if (x != par2[v][0])
cnt++;
if (cnt == 2) {
res = min(res, w);
break;
}
}
for (int i = LG - 1; i >= 0; i--)
if (h[v] - (1 << i) > h[u]) {
res = min(res, dp[v][i]);
v = par2[v][i];
}
if (par2[v][0] == u) {
cnt = 0;
for (pair<int, int> e: adj[u]) {
int x = e.first, w = e.second;
if (x != v)
cnt++;
if (cnt == 2)
return min(res, w);
}
return res;
}
if (h[v] > h[u]) {
res = min(res, dp[v][0]);
v = par2[v][0];
}
cnt = 0;
for (pair<int, int> e: adj[u]) {
int x = e.first, w = e.second;
if (x != par2[u][0])
cnt++;
if (cnt == 2) {
res = min(res, w);
break;
}
}
for (int i = LG - 1; i >= 0; i--)
if (h[u] >= (1 << i) && par2[u][i] != par2[v][i]) {
res = min(res, min(dp[u][i], dp[v][i]));
u = par2[u][i], v = par2[v][i];
}
int l = par2[u][0];
for (pair<int, int> e: adj[l]) {
int x = e.first, w = e.second;
if (x != v && x != u)
return min(res, w);
}
// cout << "---" << res << "---" << endl;
return res;
}
int getMinimumFuelCapacity(int u, int v) {
int res = lca(u, v);
// cout << res << '\n';
int tmp = min(max(lp[u], lp[v]), lca2(u, v));
// cout << lp[u] << ' ' << lp[v] << ' ' << lca2(u, v) << '\n';
if (max(res, tmp) > 1e9) return -1;
return max(res, tmp);
}
