#include "swap.h"
#include <vector>
#include <utility>
#include <iostream>
#include <algorithm>
std::vector<int> r[100010];
std::vector<std::pair<int, int> > w, w1;
int mx_ = 0;
int subt = 1;
bool cmp(std::pair<int, int> a, std::pair<int, int> b) {
return a.first < b.first;
}
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
std::vector<int> next[N + 1];
for(int i = 0; i < M; i++) {
r[U[i]].push_back(i);
r[V[i]].push_back(i);
next[U[i]].push_back(V[i]);
next[V[i]].push_back(U[i]);
mx_ = std::max(mx_, W[i]);
w.push_back({W[i], i});
w1.push_back({W[i], i});
}
for(int i = 0; i < N; i++)
if(next[i].size() != 2)
mx_ = -1;
if(N > 3 && M == N - 1 && next[0].size() == M)
subt = 2;
sort(w.begin(), w.end(), cmp);
}
int getMinimumFuelCapacity(int X, int Y) {
if(subt == 1)
return mx_;
std::vector<std::pair<int, int> > W = w;
std::vector<std::pair<int, int> > W1 = w1;
if(X > Y)
std::swap(X, Y);
int a = W1[r[X].back()].first;
int b = W1[r[Y].back()].first;
std::pair<int, int> x = W1[r[X].back()];
std::pair<int, int> y = W1[r[Y].back()];
if(X == 0) {
a = b;
x = y;
}
int mx = std::max(a, b);
if(std::lower_bound(W.begin(), W.end(), x) != W.end())
W.erase(std::lower_bound(W.begin(), W.end(), x));
if(X != 0 && std::lower_bound(W.begin(), W.end(), y) != W.end())
W.erase(std::lower_bound(W.begin(), W.end(), y));
return std::max(mx, W[0].first);
}
