#include "swap.h"
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,pao=b;i<pao;++i)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
const int MAXN=3e5+5,LOG=20,INF=1e9+7;
int n,m;
int z[MAXN],r[MAXN],up[MAXN][LOG],par[MAXN],tam[MAXN],deg[MAXN],dep[MAXN],dp[MAXN];
vector<int>chi[MAXN];
bool info[MAXN];
struct Edge{
int a,b,c;
bool operator<(const Edge&o)const{
return c<o.c;
}
};
int find(int x){
while(par[x]!=x)x=par[x];
return x;
}
void dsu(int a,int b){
if(tam[a]<tam[b])swap(a,b);
tam[a]+=tam[b];
par[b]=a;
}
void dfs(int u,int p,int d){
dep[u]=d;
for(auto v:chi[u]){
if(v==p)continue;
up[v][0]=u;
dp[v]=min(dp[v],dp[u]);
dfs(v,u,d+1);
}
}
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n=N,m=M;
vector<Edge>e;
fore(i,0,m){
e.pb({U[i],V[i],W[i]});
}
sort(ALL(e));
int nxt=n;
iota(r,r+n+m,0);
iota(par,par+n,0);
mset(tam,1);
for(auto[a,b,c]:e){
int ca=find(a),cb=find(b);
deg[a]++;deg[b]++;
z[nxt]=c;
if(ca!=cb){
chi[nxt].pb(r[ca]);
chi[nxt].pb(r[cb]);
dsu(a,b);
info[nxt]=info[r[ca]]|info[r[cb]];
r[ca]=r[cb]=nxt;
}else{//tengo ciclo
chi[nxt].pb(r[ca]);
info[nxt]=true;
r[ca]=nxt;
}
if(deg[a]>=3||deg[b]>=3)info[nxt]=true;
nxt++;
}
fore(i,0,nxt){
dp[i]=INF;
if(info[i])dp[i]=z[i];
}
dfs(nxt-1,nxt-1,0);
fore(i,1,LOG){
fore(j,0,nxt){
up[j][i]=up[up[j][i-1]][i-1];
}
}
}
int jump(int a, int d){
fore(i,0,LOG){
if(d&(1<<i))a=up[a][i];
}
return a;
}
int LCA(int a,int b){
if(dep[a]>dep[b])swap(a,b);
b=jump(b,dep[b]-dep[a]);
if(a==b)return a;
for(int i=LOG-1;i>=0;i--){
if(up[a][i]!=up[b][i]){
a=up[a][i];
b=up[b][i];
}
}
return up[a][0];
}
int getMinimumFuelCapacity(int X, int Y) {
int Z=LCA(X,Y);
if(dp[Z]==INF)return -1;
return dp[Z];
}
