#include<bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define pii pair<int,int>
#define ll long long
#define sz(x) (ll)x.size()
using namespace std;
const int mxn=1e5+5;
struct segment{
int t[2*mxn]{0};
void upd(int i,int amt,int sz){
i+=sz;t[i]=amt;
for(i>>=1;i;i>>=1)t[i]=max(t[2*i],t[2*i+1]);
}
int qr(int l,int r,int sz,int rs=0){
for(l+=sz,r+=sz;l<r;l>>=1,r>>=1){
if(l&1)rs=max(rs,t[l++]);
if(r&1)rs=max(rs,t[--r]);
}return rs;
}
}seg;
struct lazy{
int t[4*mxn]{0},lz[4*mxn]{0};
void build(){
for(int i=0;i<4*mxn;i++)t[i]=lz[i]=2e9;
}
void push(int i,int l,int r){
t[i]=min(t[i],lz[i]);
if(l<r)lz[2*i]=min(lz[2*i],lz[i]),lz[2*i+1]=min(lz[2*i+1],lz[i]);
lz[i]=2e9;
}
void upd(int i,int l,int r,int tl,int tr,int v){
push(i,l,r);
if(r<tl||l>tr)return;
if(r<=tr&&l>=tl){
lz[i]=min(lz[i],v);push(i,l,r);return;
}int m=(l+r)>>1;upd(2*i,l,m,tl,tr,v);upd(2*i+1,m+1,r,tl,tr,v);
t[i]=min(t[2*i],t[2*i+1]);
}
int qr(int i,int l,int r,int tl,int tr){
push(i,l,r);
if(r<tl||l>tr)return 2e9;
if(r<=tr&&l>=tl)return t[i];
int m=(l+r)>>1;
return min(qr(2*i,l,m,tl,tr),qr(2*i+1,m+1,r,tl,tr));
}
}lseg;
vector<pii>g[mxn];
int up[mxn]{0},pr[mxn]{0},dep[mxn]{0},head[mxn]{0},id[mxn]{0},ct=0,sz[mxn]{0},a[mxn]{0},n;
int get(int r){
return up[r]==r?r:up[r]=get(up[r]);
}
void dfs(int u,int p,int l){
pr[u]=p;dep[u]=l;sz[u]=1;
for(auto v:g[u]){
if(v.f==p)continue;
dfs(v.f,u,l+1);
a[v.f]=v.s;sz[u]+=sz[v.f];
}
}
void hld(int u,int p,int tp){
head[u]=tp;id[u]=++ct;
int hv=-1,hc=-1;
for(auto v:g[u]){
if(v.f!=p&&sz[v.f]>hc)hc=sz[v.f],hv=v.f;
}
if(hv==-1)return;
hld(hv,u,tp);
for(auto v:g[u]){
if(v.f==p||v.f==hv)continue;
hld(v.f,u,v.f);
}
}
void init(int N, int M,std::vector<int> U, std::vector<int> V, std::vector<int> W){
n=N;vector<pair<int,pii>>ed,bin;for(int i=0;i<N;i++)up[i]=i;
for(int i=0;i<M;i++)ed.pb({W[i],{U[i],V[i]}});
sort(ed.begin(),ed.end());
for(auto it : ed){
int u=get(it.s.f),v=get(it.s.s);
if(u==v){bin.pb(it);continue;}
up[u]=v;g[it.s.f].pb({it.s.s,it.f});
g[it.s.s].pb({it.s.f,it.f});
}dfs(0,0,0);hld(0,0,0);for(int i=0;i<N;i++)seg.upd(id[i]-1,a[i],N);
lseg.build();
for(auto it : bin){
int u=it.s.f,v=it.s.s;
while(head[u]!=head[v]){
if(dep[head[u]]<dep[head[v]])swap(u,v);
lseg.upd(1,1,N,id[head[u]],id[u],it.f);
u=pr[head[u]];
}
if(dep[u]>dep[v])swap(u,v);
lseg.upd(1,1,N,id[u]+1,id[v],it.f);
}
}
int getMinimumFuelCapacity(int X, int Y){
int rs1=0,rs2=2e9,x=X,y=Y;
while(head[x]!=head[y]){
if(dep[head[x]]<dep[head[y]])swap(x,y);
rs1=max(rs1,seg.qr(id[head[x]]-1,id[x],n));
rs2=min(rs2,lseg.qr(1,1,n,id[head[x]],id[x]));
x=pr[head[x]];
}if(dep[x]>dep[y])swap(x,y);
rs1=max(rs1,seg.qr(id[x],id[y],n));
rs2=min(rs2,lseg.qr(1,1,n,id[x]+1,id[y]));
if(rs2==2e9)return -1;
return max(rs1,rs2);
}
