#include "swap.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
bool cmp(pair <pair <int,int>,int> a,pair <pair <int,int>,int> b){
return a.second<b.second;
}
int dsu0[100010],dsu[300010],Deg[100010],deg[300010][4],hvcyc[300010];
int prt0(int n){
if (dsu0[n]==n) return n;
return dsu0[n]=prt0(dsu0[n]);
}
void unn0(int u,int v){
dsu0[prt0(u)]=dsu0[prt0(v)];
}
int prt(int n){
if (dsu[n]==n) return n;
return dsu[n]=prt(dsu[n]);
}
void unn(int u,int v){
u=prt(u); v=prt(v);
if (u==v) return;
dsu[u]=v;
hvcyc[v]|=hvcyc[u];
for (int i=0; i<4; i++) deg[v][i]+=deg[u][i];
}
vector <int> krt[300010];
int cost[300010],ans[300010];
int dep[300010],fa[20][300010];
void dfs(int cur,int prv,int heeh){
if (prv) dep[cur]=dep[prv]+1;
fa[0][cur]=prv;
if (hvcyc[cur]||deg[cur][3]) heeh=min(heeh,cost[cur]);
ans[cur]=heeh;
for (int i:krt[cur]) dfs(i,cur,heeh);
}
int lca(int u,int v){
if (dep[u]<dep[v]) swap(u,v);
int d=dep[u]-dep[v];
for (int i=0; i<20; i++){
if (d&(1<<i)) u=fa[i][u];
}
if (u==v) return u;
for (int i=19; i>=0; i--){
if (fa[i][u]!=fa[i][v]){
u=fa[i][u];
v=fa[i][v];
}
}
return fa[0][u];
}
void init(int N,int M,vector <int> U,vector <int> V,vector <int> W){
pair <pair <int,int>,int> edg[M+1];
for (int i=1; i<=M; i++) edg[i]={{U[i-1]+1,V[i-1]+1},W[i-1]};
sort(edg+1,edg+M+1,cmp);
for (int i=1; i<=N; i++) dsu0[i]=i;
for (int i=1; i<=N; i++) deg[i][0]=1;
for (int i=1; i<=N+M; i++) dsu[i]=i;
for (int i=1; i<=M; i++){
if (prt0(edg[i].first.first)==prt0(edg[i].first.second)){
int u=prt(edg[i].first.first);
krt[N+i].push_back(u);
unn(u,N+i);
hvcyc[N+i]=1;
} else {
int u=prt(edg[i].first.first),v=prt(edg[i].first.second);
krt[N+i].push_back(u); krt[N+i].push_back(v);
unn(u,N+i); unn(v,N+i);
unn0(edg[i].first.first,edg[i].first.second);
if (Deg[edg[i].first.first]<3) deg[N+i][Deg[edg[i].first.first]]--;
if (Deg[edg[i].first.second]<3) deg[N+i][Deg[edg[i].first.second]]--;
Deg[edg[i].first.first]++; Deg[edg[i].first.second]++;
deg[N+i][min(3,Deg[edg[i].first.first])]++;
deg[N+i][min(3,Deg[edg[i].first.second])]++;
}
cost[N+i]=edg[i].second;
}
dfs(N+M,0,2e9);
for (int i=1; i<20; i++){
for (int j=1; j<=N+M; j++) fa[i][j]=fa[i-1][fa[i-1][j]];
}
}
int getMinimumFuelCapacity(int X,int Y){
X++; Y++;
int l=lca(X,Y);
int op=ans[l];
if (op>1e9) op=-1;
return op;
}
