#include <bits/stdc++.h>
#include "swap.h"
using namespace std;
vector<tuple<int, int, int>> edge;
vector<int> deg, par, cyc, ok;
int find(int u) {
if(par[u] == u) return u;
return par[u] = find(par[u]);
}
void combine(int u, int v) {
deg[u] += 1, deg[v] += 1;
int bu = u, bv = v;
u = find(u), v = find(v);
if (u == v) {
cyc[u] = ok[u] = 1;
return;
} else {
par[v] = u;
cyc[u] |= cyc[v];
ok[u] |= (max(deg[bu], deg[bv]) >= 3);
ok[u] |= cyc[u];
}
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
for(int i = 0; i < M; ++i) edge.push_back({W[i], U[i], V[i]});
sort(edge.begin(), edge.end());
deg.resize(N + 6, 0), par.resize(N + 6, 0), cyc.resize(N + 6, 0), ok.resize(N + 6, 0);
iota(par.begin(), par.end(), 0);
}
void reset(int n) {
for(int i = 0; i < n; ++i) deg[i] = 0, par[i] = i, cyc[i] = ok[i] = 0;
}
int getMinimumFuelCapacity(int X, int Y) {
int n = (int) deg.size();
for(auto [w, u, v] : edge) {
combine(u, v);
if(find(X) == find(Y) && ok[find(X)]) {
reset(n);
return w;
}
}
reset(n);
return -1;
}
