#include <bits/stdc++.h>
#include "swap.h"
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int N=1e3+5;
vector <pair <int,int> > g[N];
int d[N][N];
int n;
void init(int N, int M,vector<int> U,vector<int> V,vector<int> W) {
n=N;
for(int i=0;i<M;i++){
g[V[i]].pb({U[i],W[i]});
g[U[i]].pb({V[i],W[i]});
}
}
int getMinimumFuelCapacity(int X, int Y) {
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
d[i][j]=1e9+5;
}
}
d[X][Y]=0;
set <vector <int> > st;
st.insert({0,X,Y});
while(!st.empty()){
vector <int> v=*st.begin();
st.erase(st.begin());
int a=v[1],b=v[2];
for(auto to : g[a]){
if(to.ff!=b){
if(d[to.ff][b]>max(d[a][b],to.ss)){
st.erase({d[to.ff][b],to.ff,b});
d[to.ff][b]=max(d[a][b],to.ss);
st.insert({d[to.ff][b],to.ff,b});
}
}
}
for(auto to : g[b]){
if(to.ff!=a){
if(d[a][to.ff]>max(d[a][b],to.ss)){
st.erase({d[a][to.ff],a,to.ff});
d[a][to.ff]=max(d[a][b],to.ss);
st.insert({d[a][to.ff],a,to.ff});
}
}
}
}
if(d[Y][X]==1e9+5)d[Y][X]=-1;
return d[Y][X];
}
/*signed main(){
ios_base::sync_with_stdio();
cin.tie(0);cout.tie(0);
int n,m;
cin>>n>>m;
vector <int> a(m),b(m),c(m);
for(int i=0;i<m;i++){
cin>>a[i]>>b[i]>>c[i];
}
init(n,m,a,b,c);
int q;
cin>>q;
while(q--){
int u,v;
cin>>u>>v;
cout<<getMinimumFuelCapacity(u,v)<<"\n";
}
}*/
/*
3
1 10
3 10
8 15
2
1 2
2 3
*/
