#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int MaxN = 100005;
vector<tuple<int, int, int>> edges;
int N;
void init(int _N, int M, vector<int> U, vector<int> V, vector<int> W) {
N = _N;
for (int i = 0; i < M; i++){
edges.emplace_back(U[i], V[i], W[i]);
}
}
vector<int> g[MaxN];
vector<bool> used;
void dfs(int v){
used[v] = true;
for (int u : g[v]){
if (!used[u]) dfs(u);
}
}
bool check(int W, int X, int Y){
for (int i = 0; i < N; i++) g[i].clear();
for (auto [u, v, w] : edges){
if (w <= W){
g[u].push_back(v);
g[v].push_back(u);
}
}
used.assign(N, false);
dfs(X);
if (!used[Y]) return false;
int cnt = 0;
for (int i = 0; i < N; i++){
if (!used[i]) continue;
int deg = (int)g[i].size();
if (deg >= 3) return true;
if (deg == 1) cnt++;
}
return cnt != 2;
}
int getMinimumFuelCapacity(int X, int Y) {
int ans = -1;
int l = 0, r = 1e9;
while (l <= r){
int mid = (l + r) >> 1;
if (check(mid, X, Y)){
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return ans;
}
