#include "swap.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
typedef long long llong;
const int MAXN = 100000 + 10;
const int INF = 1e9;
int n, m;
bool vis[MAXN];
std::vector <std::pair <int,int>> g[MAXN];
bool dfs(int node, int par, int dist)
{
int deg = 0;
bool res = false;
vis[node] = true;
for (const auto &[u, d] : g[node])
{
if (d > dist)
{
continue;
}
deg++;
if (u == par)
{
continue;
}
if (vis[u])
{
res = true;
continue;
}
res |= dfs(u, node, dist);
}
res |= (deg >= 3);
return res;
}
void clearDFS(int node)
{
vis[node] = false;
for (const auto &[u, d] : g[node])
{
if (vis[u])
{
clearDFS(u);
}
}
}
bool check(int u, int v, int dist)
{
bool res = dfs(u, 0, dist) && vis[v];
clearDFS(u);
return res;
}
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
n = N; m = M;
for (int i = 0 ; i < M ; ++i)
{
U[i]++; V[i]++;
g[U[i]].emplace_back(V[i], W[i]);
g[V[i]].emplace_back(U[i], W[i]);
}
}
int getMinimumFuelCapacity(int x, int y)
{
x++; y++;
int l = 0, r = INF + 1, mid;
while (l < r - 1)
{
mid = (l + r) / 2;
if (!check(x, y, mid)) l = mid;
else r = mid;
}
if (r > INF) return -1;
return r;
}
