#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define MAX 100000
#define u second.first
#define v second.second
#define w first
lli n,m,a,b,c,dis,cont;
vector<pair<lli,pair<lli,lli> > > orden;
pair<lli,lli> uf[MAX+2];
lli grado[MAX+2],ciclo[MAX+2];
lli sube(lli act) {
if (uf[act].first == act) return act;
uf[act].first = sube(uf[act].first);
return uf[act].first;
}
void une(lli a, lli b) {
uf[b].first = a;
if (ciclo[b]) ciclo[a] = 1;
}
void init(int N, int M,std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n = N;
m = M;
rep(i,0,m-1) orden.push_back({W[i], {U[i]+1, V[i]+1} });
sort(orden.begin(), orden.end());
}
int getMinimumFuelCapacity(int X, int Y) {
X++;
Y++;
rep(i,1,n) {
uf[i] = {i,0};
grado[i] = 0;
ciclo[i] = 0;
}
for (auto act : orden) {
cont++;
a = sube(act.u);
b = sube(act.v);
grado[act.u]++;
grado[act.v]++;
if (a != b) une(a,b);
else ciclo[a] = 1;
if (grado[act.u] > uf[a].second) uf[a].second = grado[act.u];
if (grado[act.v] > uf[a].second) uf[a].second = grado[act.v];
a = sube(X);
b = sube(Y);
if (a == b) {
if (uf[a].second > 2 || ciclo[a]) return act.w;
}
}
return -1;
}
