#include "swap.h"
#include <vector>
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int MAX_N = 100005;
struct EDGE{
int x,y;
int v;
EDGE(int _x, int _y, int _v): x(_x), y(_y), v(_v){}
};
vector<EDGE> lst;
vector<pair<int, bool> > num[MAX_N];
int par[MAX_N], height[MAX_N];
int deg[MAX_N];
int val[MAX_N];
int m;
int find_par(int x, int max_val){
if(val[x] > max_val){
return x;
}
if(x == par[x]) return x;
return find_par(par[x], max_val);
}
void merge(int x, int y, int v){
deg[x]++;
deg[y]++;
bool Z = false;
if(deg[x] == 3 || deg[y] == 3) Z = true;
x = find_par(x, v);
y = find_par(y, v);
if(x == y){
num[x].push_back(pair<int, bool>(v, true));
return;
}
if(height[y] > height[x]){
swap(x,y);
}
par[y] = x;
val[y] = v;
height[x] += height[x] == height[y];
Z |= num[x].back().se | num[y].back().se;
num[x].push_back(pair<int, bool>(v, Z));
}
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
m = M;
for(int i=0;i<M;i++){
lst.push_back(EDGE(U[i], V[i], W[i]));
}
for(int i=0;i<N;i++){
par[i] = i;
height[i] = 1;
deg[i] = 0;
val[i] = -1;
num[i].push_back(pair<int, bool>(-1, 0));
}
sort(lst.begin(), lst.end(), [&](const EDGE x, const EDGE y){
return x.v < y.v;
});
int i = 0;
for(EDGE p:lst){
merge(p.x, p.y, i);
i++;
}
}
bool is_ok(int max_val, int x, int y){
x = find_par(x, max_val);
y = find_par(y, max_val);
if(x != y) return false;
int idx = lower_bound(num[x].begin(), num[x].end(), pair<int, bool>(max_val + 1, false)) - num[x].begin() - 1;
return num[x][idx].se;
}
int getMinimumFuelCapacity(int X, int Y) {
int l = 0, r = m-1;
while(l < r){
int mid = (l + r) >> 1;
if(is_ok(mid, X, Y)){
r = mid;
}else{
l = mid + 1;
}
}
return is_ok(l, X, Y) ? lst[l].v : -1;
}
