#include "swap.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
const int MAX_N=3e5+10;
int rep[MAX_N];
int val[MAX_N];
int hasExtra[MAX_N];
vector<vi> G;
void init(int n){
for(int i=0;i<=n;i++) rep[i]=i;
}
int findset(int i){
return (rep[i]==i)?i:rep[i]=findset(rep[i]);
}
bool issameset(int i,int j){
return findset(i)==findset(j);
}
void unionset(int i,int j, int value, int newPa,int n){
if(!issameset(i,j)){
int u=findset(i);
int v=findset(j);
rep[u]=newPa;
rep[v]=newPa;
val[newPa]=value;
G[newPa].push_back(u);
G[newPa].push_back(v);
hasExtra[newPa]=(u>=n && v>=n) || hasExtra[u] || hasExtra[v];
}
}
int pa[MAX_N][20];
int height[MAX_N];
void dfs(int u,int p){
height[u]=height[p]+1;
pa[u][0]=p;
for(int i=1;i<20;i++)
pa[u][i]=pa[pa[u][i-1]][i-1];
for(auto &v:G[u])
dfs(v,u);
}
int lca(int u,int v){
if(height[u]<height[v]) swap(u,v);
int d=height[u]-height[v];
for(int i=0;i<20;i++){
if(d&(1<<i))
u=pa[u][i];
}
if(u==v) return u;
for(int i=19;i>=0;i--){
if(pa[u][i]!=pa[v][i]){
u=pa[u][i];
v=pa[v][i];
}
}
return pa[u][0];
}
void init(int N, int M,
std::vector<int> U, std::vector<int> V, std::vector<int> W) {
G.resize(N+M);
vector<int> id;
for(int i=0;i<M;i++) id.push_back(i);
sort(id.begin(),id.end(),[&](int i,int j){
return W[i]<W[j];
});
height[N+M-1]=0;
init(N+M-1);
int extra=N;
for(auto &v:id){
unionset(U[v],V[v],W[v],extra,N);
extra++;
}
dfs(extra-1,extra-1);
}
int getMinimumFuelCapacity(int X, int Y) {
int lc=lca(X,Y);
if(hasExtra[lc]) return val[lc];
else{
if(lc!=pa[lc][0]) return val[pa[lc][0]];
return -1;
}
}
