#include "swap.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define ep insert
#define pb push_back
using namespace std;
struct edge{
int x,y,w;
};
const int NN=7e5+5;
int n,m,p[NN],val[NN],f[NN],c,lg[NN],deg[NN],dis[NN],par[25][NN];
pair<int,int> st[25][NN];
bool spec[NN];
edge e[NN];
vector<int> adj[NN];
bool cmp(edge x,edge y){
return x.w<y.w;
}
int getpar(int x){
if (x==p[x]) return x;
return p[x]=getpar(p[x]);
}
void link(int x,int y){
x=getpar(x);y=getpar(y);
if (x==y) return;
p[x]=y;
adj[y].pb(x);
return;
}
void dfs(int x){
st[0][++c]={dis[x],x};
f[x]=c;
for (auto u:adj[x]){
par[0][u]=x;
dis[u]=dis[x]+1;
dfs(u);
st[0][++c]={dis[x],x};
}return;
}
void build(){
for (int i=1;i<25;i++) for (int j=1;j+(1<<i)<=c+1;j++) st[i][j]=min(st[i-1][j],st[i-1][j+(1<<(i-1))]);
for (int i=1;i<25;i++) for (int j=1;j<=n+m;j++) par[i][j]=par[i-1][par[i-1][j]];
return;
}
int query(int l,int r){
if (l>r) swap(l,r);
int i=lg[r-l+1];
//cout<<l<<' '<<r<<' '<<i<<endl;
return min(st[i][l],st[i][r-(1<<i)+1]).S;
}
void init(int N, int M,
vector<int> U, vector<int> V, vector<int> W) {
for (int i=2;i<NN;i++) lg[i]=lg[i/2]+1;
n=N,m=M;dis[0]=-1;
for (int i=0;i<m;i++) e[i+1]={U[i]+1,V[i]+1,W[i]};
sort(e+1,e+1+m,cmp);
for (int i=1;i<=n+m;i++) p[i]=i;
for (int i=1;i<=m;i++){
val[i+n]=e[i].w;
deg[e[i].x]++;
deg[e[i].y]++;
if (deg[e[i].x]>=3 || deg[e[i].y]>=3) spec[i+n]=1;
int x=getpar(e[i].x),y=getpar(e[i].y);
if (x==y){
spec[i+n]=1;
link(x,i+n);
}
else{
link(x,i+n);
link(y,i+n);
}
for (auto u:adj[i+n]) spec[i+n]|=spec[u];
}
dfs(n+m);
build();
/*for (int i=0;i<5;i++){
for (int j=1;j+(1<<i)<=c+1;j++) cout<<st[i][j].S<<' ';
cout<<endl;
}*/
return;
}
int getMinimumFuelCapacity(int x, int y) {
if (!spec[n+m]) return -1;
x++;y++;
int lca=query(f[x],f[y]);
//cout<<lca<<endl;
if (spec[lca]) return val[lca];
for (int i=24;i>=0;i--){
if (par[i][lca]==0) continue;
if (spec[par[i][lca]]) continue;
lca=par[i][lca];
}
return val[par[0][lca]];
}
