#include <bits/stdc++.h>
using namespace std;
struct Edge {
int u, v, w;
bool operator < (const Edge &other) const {
return w < other.w;
}
};
const int MAXN = 100005;
const int MAXM = 200005;
int n, m;
Edge edge[MAXM];
int parent[MAXN], compSize[MAXN];
int deg[MAXN], cnt[MAXN][2];
int getRoot(int u) {
return (u == parent[u] ? u : parent[u] = getRoot(parent[u]));
}
void raiseDeg(int u) {
int r = getRoot(u);
if (deg[u]) cnt[r][deg[u] - 1]--;
deg[u]++;
if (deg[u] <= 2) cnt[r][deg[u] - 1]++;
}
void mergeSet(int u, int v) {
u = getRoot(u);
v = getRoot(v);
if (u == v) return;
parent[u] = v;
compSize[v] += compSize[u];
cnt[v][0] += cnt[u][0];
cnt[v][1] += cnt[u][1];
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
n = N;
m = M;
for (int i = 0; i < m; i++) {
edge[i + 1] = {U[i], V[i], W[i]};
}
sort(edge + 1, edge + 1 + m);
}
int getMinimumFuelCapacity(int X, int Y) {
for (int i = 0; i < n; i++) {
parent[i + 1] = i + 1;
compSize[i + 1] = 1;
deg[i + 1] = 0;
cnt[i + 1][0] = cnt[i + 1][1] = 0;
}
for (int i = 1; i <= m; i++) {
int u = edge[i].u + 1; // đổi sang 1-based
int v = edge[i].v + 1;
raiseDeg(u);
raiseDeg(v);
mergeSet(u, v);
int r = getRoot(X + 1);
if (r == getRoot(Y + 1)) {
if (cnt[r][1] != compSize[r] - 2 || cnt[r][0] != 2) {
return edge[i].w;
}
}
}
return -1;
}
