#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double dd;
typedef vector<ll> vll;
typedef pair<ll , ll> ii;
typedef vector< ii > vii;
typedef pair < pair < ll , ll > , pair < ll , ll > > cm;
typedef tuple < ll, ll, ll > tp;
#define ff first
#define ss second
#define pb push_back
#define in insert
const ll N = 3e5 + 15;
ll par[N], ok[N], n, val[N], pr[20][N];
ii p[N];
vector < ll > v[N];
ll find(ll a){
if(a == par[a]) return a;
return par[a] = find(par[a]);
}
ll eq(ii x, ii y){
if(x == y || x == make_pair(y.ss, y.ff)) return 1;
return 0;
}
void merge(ll x, ll y, ll ww){
ii w = {x, y};
x = find(x);
y = find(y);
++n;
val[n] = ww;
ok[n] = (ok[x] & ok[y]);
par[x] = par[y] = n;
par[n] = n;
v[n].pb(x);
if(x != y) v[n].pb(y);
if(ok[n]){
if(x == y){
ok[n] = 0;
}else{
bool f = 0;
ii wut;
for(auto z1 : {p[x].ff, p[x].ss}){
for(auto z2 : {p[y].ff, p[y].ss}){
if(eq(w, {z1, z2})) f = 1, wut = {z1, z2};
}
}
if(!f){
ok[n] = 0;
}else{
if(wut.ff == p[x].ff) p[n].ff = p[x].ss;
else p[n].ff = p[x].ff;
if(wut.ss == p[y].ff) p[n].ss = p[y].ss;
else p[n].ss = p[y].ff;
}
}
}
return;
}
ll d[N];
void dfs(ll s, ll _p, ll dp){
pr[0][s] = _p;
d[s] = dp;
for(ll i = 1; i < 20; i++) pr[i][s] = pr[i-1][pr[i-1][s]];
for(auto u : v[s]){
dfs(u, s, dp + 1);
}
return;
}
ll lca(ll x, ll y){
if(d[x] < d[y]) swap(x, y);
for(ll i = 19; i >= 0; i--){
if(d[x] - (1 << i) >= d[y]) x = pr[i][x];
}
if(x == y) return x;
for(ll i = 19; i >= 0; i--){
if(pr[i][x] == pr[i][y]) continue;
x = pr[i][x], y = pr[i][y];
}
return pr[0][x];
}
void init(int _n, int m, vector<int> U, vector<int> V, vector<int> W) {
n = _n;
vector < tuple < ll , ll , ll > > e;
for(ll i = 0; i < m; i++) e.pb({W[i], V[i]+1, U[i]+1});
for(ll i = 1; i <= n; i++){
par[i] = i;
p[i] = {i, i};
ok[i] = 1;
}
sort(e.begin(), e.end());
for(auto [w, x, y] : e){
merge(x, y, w);
}
dfs(n, n, 1);
return;
}
int getMinimumFuelCapacity(int x, int y) {
x++; y++;
if(ok[n] == 1) return -1;
ll cur = lca(x, y);
if(!ok[cur]) return val[cur];
for(ll i = 19; i >= 0; i--){
if(!ok[pr[i][cur]]) continue;
cur = pr[i][cur];
}
cur = pr[0][cur];
return val[cur];
}
