#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define maxs(a, b) (a = max(a, b))
const int MXN = 3e5+5, LOG = 19;
int n, h[MXN], par[MXN][LOG], dsu[MXN], sz[MXN], name[MXN], w[MXN], mx[MXN], d[MXN], timer;
bool cyc[MXN];
vector<int> g[MXN];
int find(int v) {
return v==dsu[v] ? v : dsu[v] = find(dsu[v]);
}
inline void add(int u, int v, int w) {
int uu = find(u), vv = find(v);
if(uu==vv) {
par[name[uu]][0] = timer;
g[timer].push_back(name[uu]);
mx[timer] = max({mx[name[uu]], ++d[u], ++d[v]});
::w[timer] = w;
cyc[timer] = 1;
name[uu] = timer++;
return;
}
if(sz[uu]<sz[vv]) swap(uu, vv);
par[name[uu]][0] = par[name[vv]][0] = timer;
g[timer].push_back(name[uu]); g[timer].push_back(name[vv]);
mx[timer] = max({mx[name[uu]], mx[name[vv]], ++d[u], ++d[v]});
cyc[timer] = cyc[name[uu]]|cyc[name[vv]];
::w[timer] = w;
sz[dsu[vv] = uu] += sz[vv];
name[uu] = timer++;
}
void dfs(int v) {
for(int i=1; i<LOG; i++)
par[v][i] = par[par[v][i-1]][i-1];
for(int u : g[v]) {
h[u] = h[v]+1;
dfs(u);
}
}
inline int jump(int v, int d) {
for(int i=0; i<LOG; i++)
if(d>>i&1)
v = par[v][i];
return v;
}
inline int LCA(int u, int v) {
if(h[u]<h[v]) swap(u, v);
u = jump(u, h[u]-h[v]);
if(u==v) return u;
for(int i=LOG-1; i>=0; i--)
if(par[u][i]!=par[v][i])
u = par[u][i], v = par[v][i];
return par[u][0];
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
n = N;
for(int i=0; i<N; i++) {
dsu[i] = i;
sz[i] = 1;
name[i] = i;
}
timer = N;
vector<int> ord(M);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int i, int j) {
return W[i] < W[j];
});
for(int i=0; i<M; i++) add(U[ord[i]], V[ord[i]], W[ord[i]]);
par[timer-1][0] = timer-1;
dfs(timer-1);
}
int getMinimumFuelCapacity(int X, int Y) {
if(mx[timer-1]<=2 && !cyc[timer-1]) return -1;
int v = LCA(X, Y);
if(mx[v]>=3) return w[v];
for(int i=LOG-1; i>=0; i--)
if(mx[par[v][i]]<=2 && !cyc[par[v][i]])
v = par[v][i];
return w[par[v][0]];
}
