#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int MaxN = 100005;
vector<tuple<int, int, int>> edges;
int N, M;
int parent[MaxN];
bool line[MaxN];
pair<int, int> tail[MaxN];
void make_set(int i){
parent[i] = i;
line[i] = true;
tail[i] = make_pair(i, i);
}
int leader(int x){
return parent[x] == x ? x : parent[x] = leader(parent[x]);
}
void unite(int x, int y){
int X = x, Y = y;
x = leader(x);
y = leader(y);
if (x == y){
line[y] = false;
return;
}
parent[x] = y;
if (!line[x]){
line[y] = false;
return;
}
if (!line[y]) return;
if (tail[x].first != X && tail[x].second != X){
line[y] = false;
return;
}
if (tail[y].first != Y && tail[y].second != Y){
line[y] = false;
return;
}
pair<int, int> new_tail;
new_tail.first = tail[x].first ^ tail[x].second ^ X;
new_tail.second = tail[y].first ^ tail[y].second ^ Y;
tail[y] = new_tail;
}
bool can(int x, int y){
x = leader(x);
y = leader(y);
return x == y && !line[x];
}
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++){
edges.emplace_back(W[i], U[i], V[i]);
}
sort(edges.begin(), edges.end());
}
int getMinimumFuelCapacity(int X, int Y) {
for (int i = 0; i < N; i++) make_set(i);
for (auto [w, u, v] : edges){
unite(u, v);
if (can(X, Y)) return w;
}
return -1;
}
