#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
int N, M;
vector<int> ans, dep, p;
vector<vector<int>> par;
constexpr int inf = 2e9;
void init(int n, int m, vector<int> U, vector<int> V, vector<int> W) {
N = n;
M = m;
p.resize(N + M);
iota(p.begin(), p.end(), 0);
function<int(int)> find = [&](int x) {
return x == p[x] ? x : p[x] = find(p[x]);
};
vector<int> dif(N + M, -1), three(N + M), deg(N), w(N + M);
vector<vector<int>> ch(N + M);
auto unite = [&](int x, int y, int t) {
x = find(x);
y = find(y);
dif[t] = 1;
for (int z : set<int>{x, y}) {
three[t] |= three[z];
dif[t] += dif[z];
p[z] = t;
ch[t].push_back(z);
}
};
vector<tuple<int, int, int>> edges(M);
for (int i = 0; i < M; i++) {
edges[i] = {W[i], U[i], V[i]};
}
sort(edges.begin(), edges.end());
vector<bool> f(N + M);
for (int i = 0; i < M; i++) {
auto [z, x, y] = edges[i];
if (++deg[x] == 3) {
three[find(x)] = 1;
}
if (++deg[y] == 3) {
three[find(y)] = 1;
}
w[N + i] = z;
unite(x, y, N + i);
f[N + i] = three[N + i] == 1 || dif[N + i] >= 0;
}
ans.resize(N + M);
dep.resize(N + M);
par.resize(N + M, vector<int>(20, -1));
vector<int> stk{inf};
auto dfs = [&](auto dfs, int x) -> void {
for (int i = 0; i < 19 && par[x][i] != -1; i++) {
par[x][i + 1] = par[par[x][i]][i];
}
if (f[x]) {
stk.push_back(w[x]);
}
ans[x] = stk.back();
for (int y : ch[x]) {
dep[y] = dep[x] + 1;
par[y][0] = x;
dfs(dfs, y);
}
if (f[x]) {
stk.pop_back();
}
};
for (int i = 0; i < N + M; i++) {
if (find(i) == i) {
dfs(dfs, i);
}
}
}
int getMinimumFuelCapacity(int X, int Y) {
if (p[X] != p[Y]) {
return -1;
}
if (dep[X] < dep[Y]) {
swap(X, Y);
}
for (int i = 19; i >= 0; i--) {
if (dep[X] - (1 << i) >= dep[Y]) {
X = par[X][i];
}
}
for (int i = 19; i >= 0; i--) {
if (par[X][i] != par[Y][i]) {
X = par[X][i];
Y = par[Y][i];
}
}
int Z = par[X][0];
return ans[Z] == inf ? -1 : ans[Z];
}
