#pragma GCC optimize("unroll-loops,Ofast")
#include "swap.h"
#include <bits/stdc++.h>
#define ll int
#define ln "\n"
using namespace std;
ll n, m;
vector<array<ll, 3>> e;
vector<ll> enabled;
vector<vector<ll>> A;
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n=N; m=M; A.resize(n); e.resize(m);
for (ll i=0; i<m; i++){
e[i] = {U[i], V[i], W[i]};
A[U[i]].push_back(i); A[V[i]].push_back(i);
}
}
vector<ll> vis;
ll cnt1, cnt2, apos, req;
void dfs(ll u, ll to){
vis[u]=1; cnt1++; ll cct=0; if (u==to) req=1;
for (auto i:A[u]){
ll v = e[i][0]^e[i][1]^u;
if (!enabled[i]) continue;
cnt2++; cct++;
if (!vis[v]) dfs(v, to);
}
if (cct>=3) apos=1;
}
int getMinimumFuelCapacity(int X, int Y) {
ll l=0, r=2e9;
while (l+1<r){
ll mid = l+(r-l)/2;
enabled.assign(m, 0); vis.assign(n, 0);
for (ll i=0; i<m; i++){
if (e[i][2]<=mid) enabled[i]=1;
}
vis.assign(n, 0); cnt1=0, cnt2=0, apos=0, req=0;
dfs(X, Y);
if (req and (apos or (cnt2/2>=cnt1))){
r=mid;
}else l=mid;
}
return (r==2e9?-1:r);
}
