#include "swap.h"
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10, inf = 2e9, Log = 25;
int n, m, up[N], vp[N], wp[N], h[N], ans[N], par[N][Log], p[N], tim;
vector<int> sor;
vector<int> child[N];
struct node {
int par, sz, s, e, ans;
bool isp;
node() {
par = sz = isp = s = e = 0;
ans = inf;
}
} x[N << 2];
bool cmp(int i, int j) {
return wp[i] < wp[j];
}
int find(int u) {
if(p[u] == u) return u;
return p[u] = find(p[u]);
}
void merge(int u, int v, int t) {
int X = find(u), Y = find(v);
if(X == Y) {
if(x[X].ans == inf) {
x[X].ans = t;
x[X].isp = 0;
}
return;
}
child[tim].push_back(X), child[tim].push_back(Y);
x[tim].sz = x[X].sz + x[Y].sz;
x[X].par = tim, x[Y].par = tim, p[X] = tim, p[Y] = tim;
if(x[X].isp == 0 || x[Y].isp == 0) {
x[tim].isp = 0;
x[tim].ans = t;
}
else {
if((u == x[X].s || u == x[X].e) && (v == x[Y].s || v == x[Y].e)) {
x[tim].isp = 1;
x[tim].ans = inf;
x[tim].s = (u == x[X].s) ? (x[X].e) : (x[X].s);
x[tim].e = (v == x[Y].s) ? (x[Y].e) : (x[Y].s);
}
else {
x[tim].isp = 0;
x[tim].ans = t;
}
}
tim++;
}
void dfs(int u, int p) {
ans[u] = min(ans[u], x[u].ans);
par[u][0] = p;
for(int i = 1; i < Log; i++) par[u][i] = par[par[u][i - 1]][i - 1];
for(auto i : child[u]) {
h[i] = h[u] + 1;
ans[i] = ans[u];
dfs(i, u);
}
}
int get_par(int u, int y) {
for(int i = 0; i < Log; i++) {
if((y >> i) & 1) u = par[u][i];
}
return u;
}
int lca(int u, int v) {
if(h[u] > h[v]) swap(u, v);
v = get_par(v, h[v] - h[u]);
if(u == v) return u;
for(int i = Log - 1; i >= 0; i--) {
if(par[u][i] != par[v][i]) {
u = par[u][i], v = par[v][i];
}
}
return par[u][0];
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
n = N, m = M;
for(int i = 0; i < m; i++) {
up[i] = U[i], vp[i] = V[i], wp[i] = W[i];
sor.push_back(i);
}
sort(sor.begin(), sor.end(), cmp);
tim = n;
for(int i = 0; i < 2 * n; i++) {
p[i] = i;
x[i].par = i, x[i].sz = 1, x[i].e = i, x[i].s = i, x[i].isp = 1;
}
for(auto i : sor) {
merge(up[i], vp[i], wp[i]);
}
for(int i = 0; i < 2 * N; i++) ans[i] = inf;
dfs(tim - 1, tim - 1);
}
int getMinimumFuelCapacity(int X, int Y) {
int lc = lca(X, Y);
if(ans[lc] >= inf) return -1;
return ans[lc];
}
