#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 5;
const int LOG = 20;
int par[maxn], C[maxn], deg[maxn], dp[maxn], P[maxn], ok[maxn], G[maxn], d[maxn], n, m, N, up[maxn][LOG];
vector<int> graph[maxn];
vector<array<int, 3> > edges;
int find(int u) {
if(u == par[u]) return u;
return par[u] = find(par[u]);
}
void uni(int a, int b) {
a = find(a); b = find(b); n++;
if(a == b) C[n] = 1;
par[n] = par[a] = par[b] = n;
if(G[a] || G[b]) G[n] = 1;
if(C[a] || C[b]) C[n] = 1;
graph[n].push_back(a);
if(a != b) graph[n].push_back(b);
}
void dfs(int u, int last) {
for(int i=1; i<LOG; i++) up[u][i] = up[up[u][i-1]][i-1];
if(ok[u]) last = u;
dp[u] = last;
for(int &v : graph[u]) {
d[v] = d[u] + 1;
up[v][0] = u;
P[v] = u;
dfs(v, last);
}
}
int get_lca(int a, int b) {
if(d[a] < d[b]) swap(a, b);
int D = d[a] - d[b];
for(int j=LOG-1; j>=0; j--)
if(D & (1 << j)) a = up[a][j];
if(a == b) return a;
for(int j=LOG-1; j>=0; j--)
if(up[a][j] != up[b][j]) a = up[a][j], b = up[b][j];
return up[a][0];
}
void init(int _N, int _M, vector<int> U, vector<int> V, vector<int> W) {
n = _N; N = _N; m = _M;
for(int i=1; i<=_N+_M; i++) par[i] = i;
for(int i=0; i<m; i++) edges.push_back({ W[i], U[i] + 1, V[i] + 1});
sort(edges.begin(), edges.end());
for(auto &[w, u, v] : edges) {
deg[u]++; deg[v]++;
if(deg[u] >= 3 || deg[v] >= 3) G[n+1] = 1;
uni(u, v);
}
for(int i=1; i<=n; i++) ok[i] = (G[i] || C[i]);
dfs(n, -1);
}
int getMinimumFuelCapacity(int X, int Y) {
int L = get_lca(X+1, Y+1);
if(dp[L] == -1) return -1;
return edges[dp[L]-N-1][0];
}
