#include "swap.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
long long n, m, i, j, sz[200001], p[200001], d[200001], mx[200001], szm[200001], kek[200001];
multiset<pair<long long, long long>> ms;
int mxx;
bool st1, st2;
vector<pair<long long, long long>> g[200001];
vector<pair<long long, pair<long long, long long>>> gg;
long long get(long long x) {
return x == p[x] ? x : p[x] = get(p[x]);
}
void merge(long long xx, long long yy) {
long long x = get(xx), y = get(yy);
mx[x] = max({mx[x], d[x], d[xx]});
mx[y] = max({mx[y], d[y], d[yy]});
mx[x] = max(mx[x], mx[y]);
mx[y] = max(mx[y], mx[x]);
szm[x]++;
if (x == y) return;
if (sz[x] < sz[y]) swap(x, y);
p[y] = x;
sz[x] += sz[y];
szm[x] += szm[y];
mx[x] = max(mx[x], mx[y]);
mx[y] = max(mx[y], mx[x]);
}
void init(int N, int M,
std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n = N, m = M;
st2 = 1;
for (long long i = 0; i < M; i++) {
g[U[i]].push_back({V[i], W[i]});
g[V[i]].push_back({U[i], W[i]});
if (U[i]) {
st2 = 0;
}
gg.push_back({W[i], {U[i], V[i]}});
kek[V[i]] = W[i];
mxx = max(mxx, W[i]);
}
if (st2) {
for (long long i = 0; i < N; i++) ms.insert({kek[i], i});
}
st1 = 1;
for (long long i = 0; i < N; i++) {
if (g[i].size() > 2) st1 = 0;
}
sort(gg.begin(), gg.end());
}
bool check(long long md, long long x, long long y) {
if (md < 0 || md >= gg.size()) return 0;
for (long long i = 0; i < n; i++) sz[i] = 1, p[i] = i, d[i] = mx[i] = szm[i] = 0;
for (long long i = 0; i <= md; i++) {
d[gg[i].second.first]++;
d[gg[i].second.second]++;
merge(gg[i].second.first, gg[i].second.second);
}
if (get(x) != get(y)) return 0;
if (mx[get(x)] <= 2 && szm[get(x)] < sz[get(x)]) return 0;
return 1;
}
int getMinimumFuelCapacity(int X, int Y) {
if (st1) {
if (n == m) return mxx;
return -1;
}
if (st2) {
if (ms.size() > 2) {
ms.erase({kek[X], X});
ms.erase({kek[Y], Y});
long long ans = max({kek[X], kek[Y], (gg[2].first)});
ms.insert({kek[X], X});
ms.insert({kek[Y], Y});
return ans;
}
return -1;
}
long long l = 0, r = (int)gg.size(), md, ans = 0;
while (l <= r) {
md = (l + r) / 2;
if (check(md, X, Y)) ans = md, r = md - 1;
else l = md + 1;
}
if (!check(ans, X, Y)) return -1;
return gg[ans].first;
}
