#include "swap.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
const int MX=3e5+5;
int sz[MX];
int p[MX][20];
int nn,n;
int pr[MX];
int w[MX];
int dth[MX];
int b[MX];
int E[MX];
int c[MX];
int deg[MX];
int mdeg[MX];
vector<int> a[MX];
struct A{
int u,v,w;
bool operator <(const A&r)const{
return w<r.w;
}
}e[MX];
int lca(int v,int u){
int i,j;
if(dth[v]>dth[u])swap(u,v);
for(i=19 ; i>=0 ; i--)if(dth[u]-dth[v]>=(1<<i))u=p[u][i];
if(u==v)return v;
for(i=19 ; i>=0 ; i--){
if(p[u][i]!=p[v][i]){
u=p[u][i];
v=p[v][i];
}
}
return p[v][0];
}
int f(int k){
return k==pr[k] ? k:pr[k]=f(pr[k]);
}
void Union(A k){
deg[k.u]++;
deg[k.v]++;
int x=f(k.u);
int y=f(k.v);
if(x==y){
E[x]++;
mdeg[x]=max({mdeg[x],deg[k.u],deg[k.v]});
if(b[x]==-1)
b[x]=k.w;
return;
}
pr[x]=nn;
pr[y]=nn;
mdeg[nn]=max({mdeg[x],mdeg[y],deg[k.u],deg[k.v]});
sz[nn]=sz[x]+sz[y];
E[nn]=E[x]+E[y]+1;
w[nn]=k.w;
a[nn].push_back(x);
a[nn].push_back(y);
p[x][0]=nn;
p[y][0]=nn;
if(E[nn]>=sz[nn] && b[nn]==-1 ){
b[nn]=k.w;
}
if(mdeg[nn]>=3 && b[nn]==-1)
b[nn]=k.w;
nn++;
}
void dfs(int v,int pp){
if(E[v]>=sz[v] || mdeg[nn]>=3)c[v]=v;
else if(p[v][0]>=0)c[v]=c[p[v][0]];
else c[v]=-1;
for(auto u:a[v]){
if(u==pp)continue;
dth[u]=dth[v]+1;
dfs(u,v);
}
}
void init(int N, int M,std::vector<int> U, std::vector<int> V, std::vector<int> W) {
nn=n=N;
int i,j;
for(i=0 ; i<M; i++){
e[i]={U[i],V[i],W[i]};
}
sort(e,e+M);
for(i=0 ;i<N ; i++)sz[i]=1;
for(i=0 ; i<N+M ; i++)pr[i]=i,p[i][0]=-1,b[i]=-1;
for(i=0 ; i<M ; i++){
Union(e[i]);
}
for(i=0 ; i<nn ; i++)
if(p[i][0]==-1)
dfs(i,-1);
for(i=1 ; i<20 ; i++){
for(j=0 ; j<nn ; j++){
p[j][i]=p[p[j][i-1]][i-1];
}
}
}
int getMinimumFuelCapacity(int X, int Y) {
int k=lca(X,Y);
if(c[k]==-1)return -1;
return b[c[k]];
}
