#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e5+5;
int n, m, used[MAX], inf;
vector <pair <int, int>> g[MAX];
void init (int N, int M, vector <int> U, vector <int> V, vector <int> W) {
n = N;
m = M;
int inf = 0;
for (int i = 0; i < M; i ++) {
g[U[i]].push_back({V[i], W[i]});
g[V[i]].push_back({U[i], W[i]});
inf = max(inf, W[i]);
}
}
void dfs (int v, int p, int k, int& flag){
used[v] = 1;
int deg = 0;
for (auto i: g[v]) {
if (i.second <= k and i.first != p and used[i.first] == 1)
flag = 1;
if (i.second <= k and !used[i.first])
dfs(i.first, v, k, flag);
if (i.second <= k)
deg ++;
}
if (deg >= 3) flag = 1;
used[v] = 2;
}
bool isPossible (int a, int b, int k) {
memset(used, 0, sizeof(used));
int flag = 0;
dfs(a, -1, k, flag);
if (flag and used[b]) return true;
else return false;
}
int getMinimumFuelCapacity (int X, int Y) {
int l = 1, r = inf, best = -1;
while (l <= r) {
int mid = (l + r) / 2;
if (isPossible(X, Y, mid)) {
best = mid;
r = mid - 1;
}
else {
l = mid + 1;
}
}
return best;
}
