#include <bits/stdc++.h>
#define FOR(i,l,r) for(int i=(l); i<=(r); ++i)
#define REP(i,l,r) for(int i=(l); i<(r); ++i)
#define FORD(i,r,l) for(int i=(r); i>=(l); --i)
#define REPD(i,r,l) for(int i=(r)-1; i>=(l); --i)
#define getbit(x, i) (((x) >> (i)) & 1)
using namespace std;
const int N = 200005, logN = 19;
int n, depth[N], deg[N], dsu[N], isAny[N], ans[N];
int p[N][logN];
vector<int> S[N];
int DAD(int u) {
return dsu[u] < 0 ? u : dsu[u] = DAD(dsu[u]);
}
void Union(int u, int v, int w) {
int pu = DAD(u);
int pv = DAD(v);
if (pu == pv) {
if (!isAny[pu]) {
isAny[pu] = true;
ans[pu] = w;
}
return;
}
int p_uv = n++;
dsu[pu] = dsu[pv] = p_uv;
S[p_uv].push_back(pu);
S[p_uv].push_back(pv);
isAny[p_uv] = (isAny[pu] || isAny[pv] || deg[u] > 1 || deg[v] > 1);
if (isAny[p_uv]) ans[p_uv] = w;
++deg[u];
++deg[v];
}
void DFS(int u, int pa) {
if (!isAny[u] && isAny[pa]) {
isAny[u] = true;
ans[u] = ans[pa];
}
depth[u] = depth[pa] + 1;
p[u][0] = pa;
REP(i, 1, logN) p[u][i] = p[p[u][i - 1]][i - 1];
for(int v : S[u]) DFS(v, u);
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
n = N;
fill(dsu, dsu + n*2, -1);
vector<int> tmp;
REP(i, 0, M) tmp.push_back(i);
sort(tmp.begin(), tmp.end(), [&] (int x, int y) { return W[x] < W[y]; });
for(int id : tmp) {
Union(U[id], V[id], W[id]);
}
REP(i, 0, logN) p[n][i] = n;
DFS(n - 1, n);
}
int LCA(int u, int v) {
if (depth[u] > depth[v]) swap(u, v);
int diff = depth[v] - depth[u];
REPD(i, logN, 0) if (getbit(diff, i)) v = p[v][i];
REPD(i, logN, 0) if (p[u][i] != p[v][i]) u = p[u][i], v = p[v][i];
return u == v ? u : p[u][0];
}
int getMinimumFuelCapacity(int u, int v) {
int pa = LCA(u, v);
return isAny[pa] ? ans[pa] : -1;
}
