#include "swap.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define long long ll
int n,m;
vector<pair<int,int> >adj[200001];
bool vis1[200001];
map<int,int>mp;
bool ok=0;
int idx=1;
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
n=N,m=M;
for(int i=0;i<M;i++){
int x=U[i],y=V[i],c=W[i];
adj[x].push_back({y,c});
adj[y].push_back({x,c});
}
}
int dfs1(int u,int des){
if(u==des)
return 0;
vis1[u]=1;
int ret=1e9+5;
for(auto v:adj[u])
if(!vis1[v.first])
ret=min(ret,max(v.second,dfs1(v.first,des)));
return ret;
}
int cost=-1;
void dfs2(int u,int des,int c=0){
if(u==des){
if(cost==c)
ok=1;
return;
}
vis1[u]=1;
for(auto v:adj[u]){
if(!vis1[v.first]){
dfs2(v.first,des,max(c,v.second));
if(ok){
mp[v.first]=idx;
idx++;
return;
}
}
}
return;
}
int dfs3(int u,int des,int i=1){
if(u==des)
return 0;
vis1[u]=1;
int ret=1e9+5;
for(auto v:adj[u]){
if(!vis1[v.first]&&mp[v.first]!=i){
int c=max(v.second,dfs3(v.first,des,i+1));
ret=min(ret,c);
}
}
return ret;
}
int getMinimumFuelCapacity(int x, int y) {
mp.clear();
ok=0;
idx=1;
cost=-1;
for(int i=0;i<n;i++)vis1[i]=0;
cost=dfs1(x,y);
for(int i=0;i<n;i++)vis1[i]=0;
dfs2(x,y);
int mx=0;
for(int i=0;i<n;i++)
mx=max(mx,mp[i]);
mx++;
for(int i=0;i<n;i++){
if(!mp[i])continue;
mp[i]=mx-mp[i];
}
for(int i=0;i<n;i++)vis1[i]=0;
int path2=dfs3(x,y);
return (max(cost,path2)==(int)1e9+5?-1:max(cost,path2));
}
