#include<bits/stdc++.h>
#include "swap.h"
#define MAXN 100007
using namespace std;
const int inf=1e9+7;
int n,m,a[MAXN],b[MAXN],c[MAXN],dep[MAXN];
vector<int> tree[MAXN],v[MAXN];
int parent[MAXN],res[MAXN];
struct edge{
int from,to,cost;
inline friend bool operator < (edge fr,edge sc){
return fr.cost<sc.cost;
}
}e[MAXN];
struct unionfind{
int dsu[MAXN];
void init(){
for(int i=1;i<=n;i++)dsu[i]=i;
}
int root(int x){
if(dsu[x]==x)return dsu[x];
return root(dsu[x]);
}
void mergev(int x,int y){
if(root(x)==root(y))return;
dsu[root(x)]=root(y);
}
bool connected(int x,int y){
return root(x)==root(y);
}
}graph;
void dfs(int x,int p){
parent[x]=p;
dep[x]=dep[p]+1;
for(int i:tree[x]){
if(i==p)continue;
dfs(i,x);
}
}
pair<int,int> dp[MAXN][20];
bool li[MAXN][20];
pair<int,int> ff(int x,int p){
if(p==0)return {parent[x],min(res[x],res[parent[x]])};
if(x==0)return {0,inf};
if(li[x][p])return dp[x][p];
li[x][p]=true;
dp[x][p].first=ff(ff(x,p-1).first,p-1).first;
dp[x][p].second=min( ff(x,p-1).second , ff(ff(x,p-1).first,p-1).second );
return dp[x][p];
}
int getbranch(int x,int y){
int ans=inf;
if(dep[x]<dep[y])swap(x,y);
if(x==y or parent[x]==y)return inf;
if(dep[x]!=dep[y]){
x=parent[x];
for(int i=19;i>=0;i--){
if(dep[x]-dep[y]>(1<<i)){
ans=min(ans,ff(x,i).second);
x=ff(x,i).first;
}
}
if(parent[x]==y)return ans;
if(dep[x]>dep[y]){
x=parent[x];
ans=min(ans,res[x]);
}
}
x=parent[x];
y=parent[y];
ans=min(ans,res[x]);
for(int i=19;i>=0;i--){
if(ff(x,i).first!=0 and ff(y,i).first!=0 and ff(x,i).first!=ff(y,i).first){
ans=min(ans,ff(x,i).second);
ans=min(ans,ff(y,i).second);
x=ff(x,i).first; y=ff(y,i).first;
}
}
if(x!=y)ans=min(ans,res[parent[x]]);
return ans;
}
void init(int N, int M,vector<int> U, vector<int> V, vector<int> W) {
n=N; m=M;
for(int i=1;i<=m;i++){
a[i]=U[i-1]+1; b[i]=V[i-1]+1; c[i]=W[i-1];
v[a[i]].push_back(c[i]);
v[b[i]].push_back(c[i]);
e[i]={a[i],b[i],c[i]};
}
for(int i=1;i<=n;i++){
sort(v[i].begin(),v[i].end());
res[i]=inf;
if(v[i].size()>=3)res[i]=v[i][2];
}
res[0]=inf;
sort(e+1,e+m+1);
graph.init();
for(int i=1;i<=m;i++){
if(graph.connected(e[i].from,e[i].to))continue;
tree[e[i].from].push_back(e[i].to);
tree[e[i].to].push_back(e[i].from);
graph.mergev(e[i].from,e[i].to);
}
dfs(1,0);
}
int getMinimumFuelCapacity(int X, int Y) {
int ans=getbranch(X+1,Y+1);
if(ans==inf)return -1;
return ans;
}
/*
int main(){
init(5, 6, {0, 0, 1, 1, 1, 2}, {1, 2, 2, 3, 4, 3}, {4, 4, 1, 2, 10, 3});
cout<<getMinimumFuelCapacity(1, 2)<<"\n";
cout<<getMinimumFuelCapacity(2,4)<<"\n";
cout<<getMinimumFuelCapacity(0,1)<<"\n";
}
*/
