#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
#define all(x) (x).begin(),(x).end()
#define X first
#define Y second
#define sep ' '
#define endl '\n'
#define debug(x) cerr << #x << ": " << x << endl;
const ll MAXN = 1e6 + 10;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; // 998244353; // 1e9 + 9;
int n, m, P[MAXN], H[MAXN], deg[MAXN], E[MAXN];
vector<int> C[MAXN];
vector<pll> par[MAXN];
vector<pair<ll, pll>> edges;
inline void Union(int v, int u, int ind) {
deg[v]++;
deg[u]++;
bool B = (deg[v] > 2 || deg[u] > 2);
v = P[v], u = P[u];
if (v == u) {
E[v]++;
if ((B || E[v] >= C[v].size()) && H[v] < 0)
for (int e : C[v])
H[e] = ind;
return;
}
if (C[v].size() > C[u].size()) swap(v, u);
E[u] += E[v] + 1;
B |= (E[u] >= C[u].size() + C[v].size());
B |= (H[v] >= 0 || H[u] >= 0);
if (B) {
if (H[v] < 0)
for (int e : C[v])
H[e] = ind;
if (H[u] < 0)
for (int e : C[u])
H[e] = ind;
}
for (int e : C[v]) {
C[u].push_back(e);
par[e].push_back({ind, u});
P[e] = u;
}
C[v].clear();
}
inline int Par(int v, int t) {
auto it = lower_bound(all(par[v]), make_pair(t + 1, -1));
it--;
return it -> Y;
}
void init(int N, int M,
std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n = N, m = M;
for (int i = 1; i <= n; i++) {
P[i] = i;
C[i].push_back(i);
par[i].push_back({-1, i});
H[i] = -1;
}
for (int i = 0; i < m; i++) {
int v = V[i] + 1, u = U[i] + 1, w = W[i];
edges.push_back({w, {v, u}});
}
sort(all(edges));
for (int i = 0; i < m; i++)
Union(edges[i].Y.X, edges[i].Y.Y, i);
}
int getMinimumFuelCapacity(int u, int v) {
u++;
v++;
if (H[u] < 0 || H[v] < 0 || P[v] != P[u]) return -1;
int L = 0, R = m - 1;
while (L < R) {
int mid = (L + R) >> 1;
if (H[u] <= mid && H[v] <= mid && Par(v, mid) == Par(u, mid)) R = mid;
else L = mid + 1;
}
return edges[L].X;
}
