#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
using tint = array <int, 3>;
const int mxN = 100005, INF = 2e9;
tint edge[mxN];
int n, m, deg[mxN];
struct dsu {
array <int, 3> G[mxN]; // node, is cycle, is deg3
void init(){
for (int i = 0; i < n; i++) G[i] = {i, 0, 0};
}
int find(int x){
if (G[x][0] != x) G[x][0] = find(G[x][0]);
return G[x][0];
}
void uni(int x, int y){
x = find(x), y = find(y);
if (x != y){
G[y][0] = x;
G[x][1] |= G[y][1];
G[x][2] |= G[y][2];
}
else {
G[x][1] = 1;
}
}
} dsu;
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] = {W[i], U[i], V[i]};
sort(edge, edge + m);
}
int getMinimumFuelCapacity(int X, int Y) {
int low = 0, high = m - 1, mid, ans = -1;
while (low <= high){
dsu.init();
memset(deg, 0, sizeof deg);
mid = (low + high) / 2;
for (int i = 0; i <= mid; i++){
if (++deg[edge[i][1]] >= 3) dsu.G[edge[i][1]][2] = 1;
if (++deg[edge[i][2]] >= 3) dsu.G[edge[i][2]][2] = 1;
}
for (int i = 0; i <= mid; i++){
dsu.uni(edge[i][1], edge[i][2]);
}
X = dsu.find(X), Y = dsu.find(Y);
if (X == Y && (dsu.G[X][1] || dsu.G[X][2])){
ans = mid;
high = mid - 1;
}
else low = mid + 1;
}
if (ans != -1) return edge[ans][0];
else return -1;
}
