//#include"grader.cpp"
#include"swap.h"
#include<bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
vector<pair<int,int>>g[100005];
vector<int>child[100005];
int timer,tin[100005],tout[100005],up[100005][17],sp1[100005][17],sp2[100005][17],inf=2e9,par[100005],deg[100005];
int fin(int v){
if(v==par[v])return v;
return par[v]=fin(par[v]);
}
void dfs(int v,int p,int cost){
tin[v]=++timer;
up[v][0]=p;
sp1[v][0]=cost;
for(int i=1;i<17;i++){
up[v][i]=up[up[v][i-1]][i-1];
sp1[v][i]=max(sp1[v][i-1],sp1[up[v][i-1]][i-1]);
sp2[v][i]=min(sp2[v][i-1],sp2[up[v][i-1]][i-1]);
}
for(auto to:g[v])if(to.fr!=p)dfs(to.fr,v,to.sc);
tout[v]=++timer;
}
bool upper(int a,int b){
return tin[a]<tin[b]&&tout[a]>tout[b];
}
int lca(int a,int b){
if(upper(a,b))return a;
if(upper(b,a))return b;
for(int i=16;i>=0;i--)if(!upper(up[a][i],b))a=up[a][i];
return up[a][0];
}
int fin1(int a,int p){
int res=0;
for(int i=16;i>=0;i--)
if(!upper(up[a][i],p)){
res=max(res,sp1[a][i]);
a=up[a][i];
}
return res;
}
int fin2(int a,int p){
int res=inf;
for(int i=16;i>=0;i--)
if(!upper(up[a][i],p)){
res=min(res,sp2[a][i]);
a=up[a][i];
}
return res;
}
bool cmp(pair<int,int>l,pair<int,int>r){
return l.sc<r.sc;
}
void add_edge(int a,int b,int c){
int aa=fin(a),bb=fin(b);
deg[a]++;
deg[b]++;
if(aa!=bb){
if( sp2[aa][0]==inf && ( sp2[bb][0]!=inf ||deg[a]==3||deg[b]==3 )){
for(int i = 0; i<child[aa].size(); i++){
sp2[child[aa][i]][0]=c;
}
child[aa].clear();
}
if( sp2[bb][0]==inf && ( sp2[aa][0]!=inf ||deg[a]==3||deg[b]==3 )){
for(int i = 0; i<child[bb].size(); i++){
sp2[child[bb][i]][0]=c;
}
child[bb].clear();
}
g[a].push_back({b,c});
g[b].push_back({a,c});
if(child[aa].size()<child[bb].size())swap(aa,bb);
par[bb]=aa;
child[aa].insert(child[aa].end(),child[bb].begin(),child[bb].end());
child[bb].clear();
}else{
if(sp2[aa][0]==inf){
for(int i = 0; i<child[aa].size(); i++){
sp2[child[aa][i]][0]=c;
}
child[aa].clear();
}
}
}
bool cmp2(pair<pair<int,int>,int>l,pair<pair<int,int>,int>r){
return l.sc<r.sc;
}
void init(int N,int M,vector<int>U,vector<int>V,vector<int>W){
for(int i=0;i<N;i++)child[i].push_back(i),par[i]=i,sp2[i][0]=inf;
vector<pair<pair<int,int>,int>>ed;
for(int i=0;i<M;i++)ed.push_back({{U[i],V[i]},W[i]});
sort(ed.begin(),ed.end(),cmp2);
for(auto to:ed)
add_edge(to.fr.fr,to.fr.sc,to.sc);
for(int i=0;i<N;i++)sort(g[i].begin(),g[i].end(),cmp);
dfs(0,0,0);
}
int getMinimumFuelCapacity(int X,int Y){
int l=lca(X,Y),res;
res=max(min(fin2(X,l),fin2(Y,l)),max(fin1(X,l),fin1(Y,l)));
if(res==inf)res=-1;
return res;
}
