#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 25;
vector <pair <int, int>> adj[MAXN];
vector <int> adj2[MAXN];
bool vis[MAXN];
int deg[MAXN];
vector <int> t;
int n;
void init (int N, int m, vector <int> u, vector <int> v, vector <int> w) {
t = w; sort(t.begin(), t.end());
n = N;
for (int i = 0; i < m; i++) {
adj[u[i]].push_back({v[i], w[i]});
adj[v[i]].push_back({u[i], w[i]});
}
}
bool flag;
int cnt2 = 0;
void dfs (int pos) {
vis[pos] = 1;
flag |= deg[pos] > 2;
//cout << pos << " " << deg[pos] << '\n';
cnt2 += deg[pos] == 1;
for (auto j : adj2[pos]) {
if (!vis[j]) {
dfs(j);
}
}
}
int getMinimumFuelCapacity (int x, int y) {
int l = 0, r = (int)t.size() - 1, ans = -1;
while (l <= r) {
int mid = (l + r) >> 1;
for (int i = 0; i < n; i++) {
adj2[i].clear(); vis[i] = 0; deg[i] = 0;
for (auto [h, z] : adj[i]) {
if (z <= t[mid]) {
adj2[i].push_back(h);
deg[i]++;
}
}
//cout << (int)adj[i].size() << " " << deg[i] << ": " << (int)adj2[i].size() << '\n';
}
flag = 0; cnt2 = 0;
dfs(x);
//cout << flag << " " << cnt2 << '\n';
if (!vis[y] || (!flag && cnt2 == 2)) {
l = mid + 1;
} else {
r = mid - 1; ans = mid;
}
}
return ans == -1 ? -1 : t[ans];
}
