#include <bits/stdc++.h>
#include "swap.h"
#define REP(i,a,b) for(int i = a; i<b; i++)
#define RREP(i,a,b) for(int i = a; i>b; i--)
using namespace std;
typedef long long ll;
vector<int> parent, comp, depth, deg;
vector<bool> swp;
vector<vector<int>> lift, dp, adj;
int nxt,n,m,lg = 19;
int find(int i){
if(parent[comp[i]] == comp[i]) return comp[i];
comp[i] = find(comp[i]);
return comp[i];
}
void merge(int u, int v, int w){
deg[u]++; deg[v]++;
int U = u, V = v;
u = find(u); v = find(v);
parent[nxt] = nxt;
lift[0][nxt] = nxt;
parent[u] = parent[v] = comp[u] = comp[v] = nxt;
swp[nxt] = (u == v)|swp[u]|swp[v]|(max(deg[U],deg[V]) == 3);
lift[0][u] = lift[0][v] = nxt;
dp[0][u] = dp[0][v] = w;
adj[nxt].push_back(u);
if(u!=v){
adj[nxt].push_back(v);
}
nxt++;
}
void dfs(int node){
for(int i: adj[node]){
depth[i] = depth[node]+1;
dfs(i);
}
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
nxt = n = N, m = M;
deg.assign(N+M,0);
depth.assign(N+M,0);
parent.resize(N+M);
comp.resize(N+M);
swp.assign(N+M,false);
lift.resize(lg+2, vector<int>(N+M));
dp.assign(lg+2, vector<int>(N+M,0));
adj.resize(N+M);
vector<int> wt(M);
iota(wt.begin(),wt.end(),0);
sort(wt.begin(),wt.end(), [&](int a, int b){
return W[a]<W[b];
});
REP(i,0,N) parent[i] = comp[i] = lift[0][i] = i;
for(int i: wt){
merge(U[i], V[i], W[i]);
}
REP(i,0,N+M){
lift[0][i] = parent[i];
}
REP(i,1,lg+1){
REP(j,0,N+M){
lift[i][j] = lift[i-1][lift[i-1][j]];
dp[i][j] = max(dp[i-1][j], dp[i-1][lift[i-1][j]]);
}
}
depth[0] = 0;
dfs(find(0));
}
int getMinimumFuelCapacity(int X, int Y) {
int res = 0;
if(depth[X]>depth[Y]) swap(X,Y);
int k = depth[Y] - depth[X];
while(k){
res = max(res, dp[__builtin_ctz(k&-k)][Y]);
Y = lift[__builtin_ctz(k&-k)][Y];
k-=k&-k;
}
if(X!=Y){
RREP(i,lg,-1){
if(lift[i][X] != lift[i][Y]){
res = max(res,max(dp[i][X], dp[i][Y]));
X = lift[i][X];
Y = lift[i][Y];
}
}
res = max(res, dp[0][X]);
X = lift[0][X];
}
if(swp[X]) return res;
RREP(i,lg, -1){
if(!swp[lift[i][X]]){
res = max(res, dp[i][X]);
X = lift[i][X];
}
}
res = max(res, dp[0][X]);
X = lift[0][X];
if(swp[X]) return res;
return -1;
}
