#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int maxn = 1000005;
long long check[maxn], par[maxn], siz[maxn], weight[maxn], rt[maxn], cnt, n, eyad[maxn], saad[maxn], jump[maxn][20];
long long in[maxn], out[maxn], d[maxn], tim;
bool flag[maxn];
vector<long long> adj[maxn];
void make(int v) {
par[v] = v;
rt[v] = v;
siz[v] = 1;
weight[v] = -1;
eyad[v] = -1;
}
int fnd(int v) {
if (par[v] == v) return v;
return par[v] = fnd(par[v]);
}
void merge(int v, int u, int w) {
check[u]++, check[v]++;
bool f = 0;
if (check[u] == 3 || check[v] == 3) f = 1;
v = fnd(v), u = fnd(u);
if (v == u) {
flag[v] = 1;
adj[cnt + n].push_back(rt[v]);
rt[v] = cnt + n;
saad[rt[v]] = 1;
weight[rt[v]] = w;
cnt++;
return;
}
if (siz[v] < siz[u]) swap(v, u);
adj[n + cnt].push_back(rt[v]);
adj[n + cnt].push_back(rt[u]);
rt[v] = n + cnt;
cnt++;
flag[v] |= f;
flag[v] |= flag[u];
saad[rt[v]] = flag[v];
weight[rt[v]] = w;
par[u] = v;
siz[v] += siz[u];
}
void dfs(int v) {
in[v] = tim++;
// cout << eyad[v] << ' ' << v << '\n';
for (int u : adj[v]) {
if (eyad[u] < 0) eyad[u] = 1e9;
if (saad[u]) eyad[u] = weight[u];
eyad[u] = min(eyad[u], eyad[v]);
d[u] = d[v] + 1;
jump[u][0] = v;
dfs(u);
}
out[v] = tim++;
}
void build() {
jump[cnt + n - 1][0] = cnt + n - 1;
for (int j = 1; j < 20; j++) {
for (int i = 0; i < n + cnt; i++) jump[i][j] = jump[jump[i][j - 1]][j - 1];
}
}
int lca(int u, int v) {
if (d[u] < d[v]) swap(u, v);
if (in[v] < in[u] && out[v] > out[u]) return v;
for (int k = 19; k >= 0; k--) {
int w = jump[v][k];
if (in[w] < in[u] && out[w] > out[u]) continue;
v = w;
}
return jump[v][0];
}
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n = N;
for (int i = 0; i < M + n; i++) make(i);
vector<array<int, 3>> e;
for (int i = 0; i < M; i++) e.push_back({W[i], U[i], V[i]});
sort(e.begin(), e.end());
reverse(e.begin(), e.end());
while(e.size()) {
auto [w, v, u] = e.back();
e.pop_back();
merge(u, v, w);
}
if (saad[cnt + n - 1]) eyad[cnt + n - 1] = weight[cnt + n - 1];
dfs(cnt + n - 1);
// cout << cnt << '\n';
// for (int i = 0; i < cnt + n; i++) cout << check[i] << ' ';
// cout << '\n';
// for (int i = 0; i < cnt + n; i++) cout << flag[i] << ' ';
// cout << '\n';
// for (int i = 0; i < cnt + n; i++) cout << weight[i] << ' ';
build();
}
int getMinimumFuelCapacity(int X, int Y) {
int w = lca(X, Y);
// cout << eyad[w] << '\n';
return eyad[w];
}
