#include "swap.h"
#include<bits/stdc++.h>
#define ll long long
#define nl "\n"
#define all(v) v.begin(),v.end()
#define baraa ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
vector<vector<array<ll, 3> > > adj;
ll n, m;
void init(int N, int M,
std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n = N, m = M;
adj = vector<vector<array<ll, 3> > >(n + 1);
for (ll i = 0; i < m; i++) {
adj[U[i]].push_back({V[i], W[i], i});
adj[V[i]].push_back({U[i], W[i], i});
}
}
int getMinimumFuelCapacity(int x, int y) {
vector<ll> used(m, 0);
auto dijk = [&](ll s, ll e) {
vector<ll> dist(n + 1, LLONG_MAX);
vector<array<ll, 2> > par(n + 1, {-1, -1});
priority_queue<array<ll, 2>, vector<array<ll, 2> >, greater<> > pq;
pq.push({dist[s] = 0, s});
par[s] = {s, -1};
// cout << s << ' ' << e << nl;
while (!pq.empty()) {
auto [c, u] = pq.top();
pq.pop();
if (c > dist[u])continue;
// cout << c << ' ' << u << nl;
for (auto [v, w, idx]: adj[u]) {
if (used[idx])continue;
if (max(c, w) < dist[v])
par[v] = {u, idx}, pq.push({dist[v] = max(c, w), v});
}
}
if (dist[e] == LLONG_MAX)return dist[e];
ll ed = e;
while (ed != s) {
used[par[ed][1]] = 1;
ed = par[ed][0];
}
return dist[e];
};
ll res = -1;
for (ll i: {0, 1})
res = max(res, dijk(x, y));
return (res == LLONG_MAX ? -1 : res);
}
