#pragma GCC optimize("Ofast,unroll-loops,fast-math")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll ;
#define pll pair<ll , ll >
#define all(x) (x).begin(),(x).end()
#define SZ(x) (ll)(x).size()
#define X first
#define Y second
#define mp make_pair
#define pii pair<int , int>
#define vec vector
#define file_io freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
// BIG p : 1000000000000037 , 100000000003
ll poww(ll a, ll b, ll md) {
return (!b ? 1 : (b & 1 ? a * poww(a * a % md, b / 2, md) % md : poww(a * a % md, b / 2, md) % md));
}
const int maxn = 2000*100+5 ;
const ll inf = 9223372036854775807 ;
const ll mod = 1e9 + 7 ;
const int lg = 20 ;
int par[lg][maxn] , sz[maxn] , mark[maxn] , d[maxn] , flag , ans , dp[maxn] , mx[lg][maxn] , h[maxn] , mo[maxn];
vec<pair<int , pii>> e ;
vec<pii> adj[maxn] ;
void dfsdown(int v , int p){
for(auto u : adj[v]){
if(u.X != p ){
dfsdown(u.X , v) ;
dp[v] = min(dp[v] , max(dp[u.X] , u.Y)) ;
}
}
}
void dfsup(int v , int p){
for(auto u : adj[v]){
if(u.X != p){
dp[u.X] = min(dp[u.X] , max(u.Y , dp[v])) ;
dfsup(u.X , v) ;
}
}
}
void dfs(int v , int p){
for(auto u : adj[v]){
if(u.X != p){
par[0][u.X] = v ;
mx[0][u.X] = u.Y ;
for(int i = 1 ; i < lg; i ++ ){
par[i][u.X] = par[i-1][par[i-1][u.X]] ;
mx[i][u.X] = max(mx[i-1][u.X] , mx[i-1][par[i-1][u.X]]) ;
}
h[u.X] = h[v] + 1 ;
dfs(u.X , v) ;
}
}
}
int lca(int u , int v){
int res = 0 ;
if(h[u] > h[v]) swap(u , v) ;
for(int i = lg-1 ; i >= 0 ; i -- ){
if(par[i][v] != -1 && h[par[i][v]] >= h[u]){
res = max(res , mx[i][v]) ;
v = par[i][v] ;
}
}
if(u == v) return res ;
for(int i = lg -1 ; i >= 0 ; i -- ){
if(par[i][v] != par[i][u]){
res = max(res , mx[i][v]) ;
res = max(res , mx[i][u]) ;
u = par[i][u] ;
v = par[i][v] ;
}
}
res = max(res , mx[0][u]) ; res = max(res , mx[0][v]) ;
return res ;
}
int getMinimumFuelCapacity(int x , int y){
if(max(lca(x , y) , dp[x]) == mod)
return -1 ;
else return max(lca(x , y) , dp[x]) ;
}
void init(int n , int m , vec<int> A , vec<int> B , vec<int> W ){
for(int i = 0 ; i < m ; i ++ ){
e.pb({W[i] , {A[i] , B[i]}}) ;
adj[A[i]].pb({B[i] , W[i]}) ;
adj[B[i]].pb({A[i] , W[i]}) ;
}
sort(all(e)) ;
for(int i = 0 ; i < maxn ; i ++ ){
dp[i] = mod ;
}
for(auto u : e){
d[u.Y.X] ++ ;
d[u.Y.Y] ++ ;
if(d[u.Y.X] == 3) dp[u.Y.X] = u.X ;
if(d[u.Y.Y] == 3) dp[u.Y.Y] = u.X ;
}
for(auto u : e){
dp[u.Y.X] = min(dp[u.Y.X] , max(u.X , dp[u.Y.Y])) ;
dp[u.Y.Y] = min(dp[u.Y.Y] , max(u.X , dp[u.Y.X])) ;
}
dfsdown(0 , -1) ;
dfsup(0 , -1) ;
h[0] = 1 ;
for(int i = 0 ; i < lg ; i ++ ) par[i][0] = -1 ;
dfs(0 , -1) ;
}
/*int main()
{
migmig ;
int n , m ;
cin>>n>>m ;
int u[m] , v[m] , w[m] ;
for(int i = 0 ; i < m ; i ++ ) cin>>u[i]>>v[i]>>w[i] ;
init(n , m , u , v , w) ;
int q ;
cin>>q ;
while(q--){
int U , V ;
cin>>U>>V ;
cout<<getMinimumFuelCapacity(U , V) << endl ;
}
}*/
