#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) int(x.size())
#define all(x) x.begin(), x.end()
#define db double
#define ll long long
#define ar array
template<typename T> bool ckmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
const int LOG = 17;
struct dsu {
vector<vector<int>> adj;
vector<int> deg, p, sub;
vector<bool> mark;
vector<vector<int>> up;
vector<int> depth, good;
int who, N;
dsu() {}
dsu(int n, int m) : N(n), adj(n + m), deg(n), p(n + m), who(n), sub(n + m), mark(n + m), up(n + m, vector<int>(LOG, -1)), depth(n + m), good(n + m, -1) {
iota(all(p), 0);
}
int get(int v) {
return v == p[v] ? v : p[v] = get(p[v]);
}
void add(int x, int y) {
int ox = x, oy = y;
x = get(x), y = get(y);
p[x] = who, p[y] = who;
if (deg[ox] == 0) sub[who] += -1;
else if (deg[ox] == 1) sub[who] += 1;
if (deg[oy] == 0) sub[who] += -1;
else if (deg[oy] == 1) sub[who] += 1;
deg[ox]++, deg[oy]++;
if (deg[ox] > 2 || deg[oy] > 2) mark[who] = 1;
adj[who].emplace_back(x);
if (x != y) adj[who].emplace_back(y);
who++;
}
void process(int sx) {
auto dfs = [&](auto&& s, int v, int p) -> void {
for (int u : adj[v]) if (u != p) {
up[u][0] = v, depth[u] = depth[v] + 1;
for (int i = 1; i < LOG; i++) {
if (~up[u][i-1]) up[u][i] = up[up[u][i-1]][i-1];
}
s(s, u, v);
sub[v] += sub[u];
mark[v] = mark[v] || mark[u];
}
};
dfs(dfs, sx, -1);
auto dfs2 = [&](auto&& s, int v, int p, int lst) -> void {
if (v >= N && (mark[v] || sub[v] == 0)) lst = v;
good[v] = lst;
for (int u : adj[v]) if (u != p) {
s(s, u, v, lst);
}
};
dfs2(dfs2, sx, -1, -1);
}
int lca(int x, int y) {
if (depth[x] < depth[y]) swap(x, y);
int diff = depth[x] - depth[y];
for (int i = 0; i < LOG; i++) if (diff >> i & 1) x = up[x][i];
assert(depth[x] == depth[y]);
for (int i = LOG-1; i >= 0; i--) if (up[x][i] != up[y][i]) x = up[x][i], y = up[y][i];
return x == y ? x : up[x][0];
}
};
const int INF = 1e9;
vector<vector<ar<int, 3>>> adj;
vector<int> weights;
int n, m;
dsu d;
void init(int N, int M,
std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n = N, m = M;
adj.resize(N + 1);
d = dsu(n, m);
for (int i = 0; i < M; i++) {
adj[U[i]].push_back({V[i], W[i], i});
adj[V[i]].push_back({U[i], W[i], i});
}
vector<int> idx(M);
iota(all(idx), 0);
sort(all(idx), [&](int x, int y) { return W[x] < W[y]; });
for (int i = 0; i < M; i++) {
d.add(U[idx[i]], V[idx[i]]);
}
d.process(n + m - 1);
weights.resize(m);
for (int i = 0; i < m; i++) {
weights[i] = W[idx[i]];
}
}
int getMinimumFuelCapacity(int X, int Y) {
int ans = d.good[d.lca(X, Y)];
return ~ans ? weights[ans - n] : -1;
}
