#include "swap.h"
#include<bits/stdc++.h>
#define ll long long
#define nl "\n"
#define all(v) v.begin(),v.end()
#define baraa ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
vector<vector<array<ll, 3> > > adj;
ll n, m;
vector<ll> weights;
void init(int N, int M,
std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n = N, m = M;
adj = vector<vector<array<ll, 3> > >(n + 1);
for (ll i = 0; i < m; i++) {
adj[U[i]].push_back({V[i], W[i], i});
adj[V[i]].push_back({U[i], W[i], i});
weights.push_back(W[i]);
}
sort(all(weights));
weights.erase(unique(all(weights)), weights.end());
}
int getMinimumFuelCapacity(int x, int y) {
ll l = 0, r = weights.size() - 1, ans = -1;
while (l <= r) {
ll mid = (l + r) / 2, ok = 0, ok2 = 0, all = 0, nodes = 0;
vector<ll> vis(n + 1, 0);
function<void(ll)> dfs = [&](ll u) {
if (vis[u])return;
vis[u] = 1;
ok |= (u == y);
ll cnt = 0;
nodes++;
for (auto [v, w, idx]: adj[u])
if (w <= weights[mid])
dfs(v), cnt++;
ok2 |= (cnt >= 3);
all += cnt;
};
dfs(x);
if (ok and (ok2 or (all / 2) > nodes - 1))ans = weights[mid], r = mid - 1;
else l = mid + 1;
}
return ans;
}
