#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];
int degree[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){
degree[i]++; degree[j]++;
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]=hasExtra[u] | hasExtra[v] | degree[u]>=3 | degree[v]>=3;
newPa++;
}
else{
int u=findset(i);
G[newPa].push_back(u);
val[u]=value;
hasExtra[u]=true;
newPa++;
}
}
class LCA{
private:
vector<vi> G;
int N;
vector<vi> pa;
public:
vi height;
LCA(){}
LCA(vector<vi> _G,int _n): G(_G),N(_n){
pa.assign(N,vi(20));
height.assign(N,0);
dfs(N-1, N-1);
}
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])
if(v!=p)
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];
}
int getAns(int lc){
for(int i=19;i>=0;i--){
if(!hasExtra[pa[lc][i]]){
lc=pa[lc][i];
}
}
if(hasExtra[lc]) return lc;
lc=pa[lc][0];
return (hasExtra[lc])?lc:-1;
}
};
LCA kru;
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];
});
init(N+M-1);
int extra=N;
for(auto &v:id){
unionset(U[v],V[v],W[v],extra,N);
}
kru = LCA(G,extra);
}
int getMinimumFuelCapacity(int X, int Y) {
int lc=kru.lca(X,Y);
int ans=kru.getAns(lc);
return (ans!=-1)?val[ans]:-1;
}
