#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 5;
const int LOG = 20;
int par[maxn+5], cycle[maxn+5], deg[maxn+5], P[maxn+5], pref[maxn+5], good[maxn+5], d[maxn+5], n, m, N, up[maxn+5][LOG];
vector<int> graph[maxn+5];
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) cycle[n] = 1;
par[n] = par[a] = par[b] = n;
if(good[a] || good[b]) good[n] = 1;
if(cycle[a] || cycle[b]) cycle[n] = 1;
graph[n].push_back(a);
if(a != b) graph[n].push_back(b);
}
void dfs(int u) {
for(int i=1; i<LOG; i++) up[u][i] = up[up[u][i-1]][i-1];
for(int &v : graph[u]) {
d[v] = d[u] + 1;
up[v][0] = u;
P[v] = u;
pref[v] = pref[u] + (good[v] || cycle[v]);
dfs(v);
}
}
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;
cycle[i] = deg[i] = good[i] = 0;
}
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) good[n+1] = 1;
if(deg[v] >= 3) good[n+1] = 1;
uni(u, v);
}
dfs(n);
}
int getMinimumFuelCapacity(int X, int Y) {
X++; Y++;
int lca = get_lca(X, Y);
if(good[lca] || cycle[lca]) return edges[lca-N-1][0];
int l=0, r=d[lca], ans=-1;
while(l <= r) {
int mid = (l + r) / 2, curr = lca;
for(int j=LOG-1; j>=0; j--) if(mid & (1 << j)) curr = up[curr][j];
if(pref[lca] - pref[P[curr]]) ans = curr, r = mid - 1;
else l = mid + 1;
}
return (ans == -1 ? -1 : edges[ans-N-1][0]);
}
