#include "swap.h"
#include<bits/stdc++.h>
using namespace std;
struct yal{
int u,v,w,vas;
bool operator <(yal b){
return w<b.w;
}
int getad(int fu){
return (fu^u^v);
}
};
const int maxn=100000+10,lg=17;
int n,m,wlca[lg][maxn],lca[lg][maxn],inf=1e9+5,mainres[maxn],timea;
vector<yal>alle;
vector<int>adjt[maxn];
pair<int,int>stf[maxn];
bool zird(int u,int v){
return stf[v].first<=stf[u].first&&stf[v].second>=stf[u].second;
}
struct dsu{
int par[maxn],val[maxn];
vector<int>allv[maxn];
dsu(){
for(int i=0;i<maxn;i++){
par[i]=i;
val[i]=inf;
allv[i].push_back(i);
}
};
int root(int u){
if(u==par[u]){
return u;
}
return par[u]=root(par[u]);
}
int con(int u,int v,int w){
int rootu=root(u),rootv=root(v);
if(rootu!=rootv){
par[rootv]=rootu;
if((int)allv[rootu].size()<(int)allv[rootv].size()){
swap(allv[rootu],allv[rootv]);
}
for(auto x:allv[rootv]){
allv[rootu].push_back(x);
}
if(val[rootu]<inf||val[rootv]<inf){
val[rootu]=w;
}
if(val[rootu]<inf){
for(auto x:allv[rootu]){
mainres[x]=min(mainres[x],val[rootu]);
}
allv[rootu].clear();
}
return 1;
}else{
return 0;
}
}
void tagh(int u,int w){
u=root(u);
for(auto x:allv[u]){
mainres[x]=min(mainres[x],w);
}
allv[u].clear();
val[u]=min(w,val[u]);
}
}ds;
int av=inf;
void dfs(int u=1,int par=-1){
timea++;
stf[u].first=timea;
for(auto x:adjt[u]){
int v=alle[x].getad(u);
if(v==par){
continue;
}
wlca[0][v]=alle[x].w;
lca[0][v]=u;
dfs(v,u);
}
stf[u].second=timea;
}
void callca(){
for(int i=1;i<lg;i++){
for(int j=1;j<=n;j++){
lca[i][j]=lca[i-1][lca[i-1][j]];
wlca[i][j]=max(wlca[i-1][j],wlca[i-1][lca[i-1][j]]);
}
}
}
int getlca(int u,int v){
if(zird(u,v)){
return v;
}
if(zird(v,u)){
return u;
}
for(int i=lg-1;i>=0;i--){
if(lca[i][u]!=0&&zird(v,lca[i][u])==0){
u=lca[i][u];
}
}
return lca[0][u];
}
int getwlca(int u,int v){
if(u==v){
return 0;
}
int ret=0;
for(int i=lg-1;i>=0;i--){
if(lca[i][u]!=0&&zird(v,lca[i][u])==0){
ret=max(ret,wlca[i][u]);
u=lca[i][u];
}
}
ret=max(ret,wlca[0][u]);
return ret;
}
void init(int N, int M,std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n=N;
m=M;
alle.resize(m);
for(int i=0;i<maxn;i++){
mainres[i]=inf;
}
for(int i=0;i<m;i++){
U[i]++;
V[i]++;
alle[i].u=U[i];
alle[i].v=V[i];
alle[i].w=W[i];
}
sort(alle.begin(),alle.end());
for(int i=0;i<m;i++){
if(ds.con(alle[i].u,alle[i].v,alle[i].w)){
alle[i].vas=1;
adjt[alle[i].u].push_back(i);
adjt[alle[i].v].push_back(i);
if((int)adjt[alle[i].u].size()>2||(int)adjt[alle[i].v].size()>2){
ds.tagh(alle[i].u,alle[i].w);
}
}else{
ds.tagh(alle[i].u,alle[i].w);
}
}
dfs();
callca();
}
int mx;
void dfsres(int u,int v){
int uv=getlca(u,v);
mx=max(getwlca(u,uv),getwlca(v,uv));
}
int getMinimumFuelCapacity(int X, int Y) {
X++;
Y++;
mx=inf;
dfsres(X,Y);
long long ret=max(mx,min(mainres[X],mainres[Y]));
if(ret>=inf){
return -1;
}
return ret;
}
