#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int n, m, used[N], flag;
vector <pair <int, int>> g[N];
vector <int> val;
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
n = N;
m = M;
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]});
val.push_back(W[i]);
}
sort(val.begin(), val.end());
}
void dfs(int v, int p, int k, int x, int y) {
used[v] = 1;
// cerr << "v = " << v << endl;
if (v != x and v != y and g[v].size() > 2) flag = 1;
for (auto i: g[v]) {
if (i.second > k or i.first == p) continue;
if (used[i.first]) flag = 1;
else dfs(i.first, v, k, x, y);
}
}
int getMinimumFuelCapacity(int X, int Y) {
int l = 0, r = m - 1, best = -1;
while (l <= r) {
int mid = (l + r) / 2;
// cerr << "mid = " << mid << endl;
flag = 0;
memset(used, 0, sizeof(used));
dfs(X, 0, val[mid], X, Y);
// cerr << "used[Y] = " << used[Y] << endl;
// cerr << "flag = " << flag << endl;
if (used[Y] and flag) {
best = val[mid];
r = mid - 1;
}
else {
l = mid + 1;
}
}
return best;
}
