#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
int N;
vector<tuple<int, int, int>> edges;
constexpr int inf = 2e9;
void init(int n, int M, vector<int> U, vector<int> V, vector<int> W) {
N = n;
for (int i = 0; i < M; i++) {
edges.emplace_back(W[i], U[i], V[i]);
}
sort(edges.begin(), edges.end());
}
int getMinimumFuelCapacity(int X, int Y) {
vector<int> p(N);
iota(p.begin(), p.end(), 0);
function<int(int)> find = [&](int x) {
return x == p[x] ? x : p[x] = find(p[x]);
};
vector<int> sz(N, 1), t(N), deg(N);
auto unite = [&](int x, int y) {
x = find(x);
y = find(y);
if (x == y) {
t[x] = 1;
return;
}
if (sz[x] > sz[y]) {
swap(x, y);
}
p[x] = y;
t[y] |= t[x];
sz[y] += sz[x];
};
for (auto [z, x, y] : edges) {
if (++deg[x] == 3) {
t[find(x)] = 1;
}
if (++deg[y] == 3) {
t[find(y)] = 1;
}
unite(x, y);
if (find(X) == find(Y)) {
if (t[p[X]]) {
return z;
}
}
}
return -1;
}
