#include<bits/stdc++.h>
#include "swap.h"
#define MAXN 100007
using namespace std;
int n,m;
struct edge{
int from,to,cost;
inline friend bool operator < (edge fr,edge sc){
return fr.cost<sc.cost;
}
}e[MAXN];
int closest[MAXN],special[MAXN];
int lt[MAXN],rt[MAXN];
vector<int> query[MAXN];
struct union_find{
vector< pair<int,int> > dsu[MAXN];
int sz[MAXN],trip[MAXN],deg[MAXN],tim;
void reset(){
for(int i=1;i<=n;i++){
dsu[i]={{i,0}}; sz[i]=1; trip[i]=deg[i]=0;
}
tim=0;
}
int root(int x){
if(dsu[x].back().first==x)return dsu[x].back().first;
return root(dsu[x].back().first);
}
void mergev(int x,int y){
tim++;
int rootx=root(x);
int rooty=root(y);
deg[x]++; deg[y]++;
if(deg[x]>=3)trip[rootx]=x;
if(deg[y]>=3)trip[rootx]=y;
if(rootx==rooty)return;
if(sz[rootx]<sz[rooty])swap(rootx,rooty);
dsu[rooty].push_back({rootx,tim});
sz[rootx]+=sz[rooty];
if(trip[rooty]!=0)trip[rootx]=trip[rooty];
}
int comp(int x,int when){
int l=0,r=dsu[x].size(),tt;
while(l+1<r){
tt=(l+r)/2;
if(dsu[x][tt].second<=when){
l=tt;
}else{
r=tt;
}
}
return dsu[x][l].first;
}
int pastroot(int x,int when){
int curr=comp(x,when);
if(curr==x)return x;
return pastroot(curr,when);
}
}graph;
void build_mst(){
graph.reset();
for(int i=1;i<=m;i++){
graph.mergev(e[i].from,e[i].to);
for(int f:query[i]){
closest[f]=graph.trip[graph.root(f)];
}
}
}
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++){
e[i]={U[i-1]+1,V[i-1]+1,W[i-1]};
}
sort(e+1,e+m+1);
for(int i=1;i<=n;i++){
lt[i]=0; rt[i]=m+1;
}
for(int i=1;i<=18;i++){
for(int f=1;f<=m;f++)query[f].clear();
for(int f=1;f<=n;f++){
query[(lt[f]+rt[f])/2].push_back(f);
}
build_mst();
for(int f=1;f<=n;f++){
if(closest[f]!=0){
rt[f]=(lt[f]+rt[f])/2;
special[f]=closest[f];
}else{
lt[f]=(lt[f]+rt[f])/2;
}
}
}
}
int getMinimumFuelCapacity(int X, int Y){
X++; Y++;
if(rt[X]==m+1)return -1;
int ans=e[max(rt[X],rt[Y])].cost;
int l=0,r=m+1,tt;
while(l+1<r){
tt=(l+r)/2;
if(graph.pastroot(X,tt)==graph.pastroot(Y,tt)){
r=tt;
}else{
l=tt;
}
}
ans=max(ans,e[r].cost);
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";
}
*/
