#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mask(x) (1LL<<(x))
typedef long long ll;
typedef pair <ll,ll> ii;
typedef pair <ll,ii> iii;
ll n,m;
ll parent[100005][20];
ll mx[100005][20];
vector <ii> vt[100005];
ll sz[100005];
ll solve(ll aa,ll bb)
{
if (aa==-1&&bb==-1)
{
return -1;
}
if (aa==-1)
{
return bb;
}
if (bb==-1)
{
return aa;
}
return min(aa,bb);
}
ll solvea(ll aa,ll bb)
{
if (aa==-1&&bb==-1)
{
return -1;
}
if (aa==-1)
{
return bb;
}
if (bb==-1)
{
return aa;
}
return max(aa,bb);
}
struct DSU{
ll lab[100005];
bool check[100005];
ll tmp[100005];
ll countedge[100005];
void makeset(int u)
{
lab[u]=-1;
tmp[u]=-1;
countedge[u]=0;
}
ll findset(int u)
{
if (lab[u]<0)
{
return u;
}
return lab[u]=findset(lab[u]);
}
void Union(int u,int v,ll w)
{
int r=findset(u);
int s=findset(v);
countedge[u]++;
countedge[v]++;
if (r==s)
{
if (tmp[r]==-1)
{
tmp[r]=w;
}
return;
}
if (lab[r]>lab[s])
{
swap(r,s);
}
lab[r]+=lab[s];
lab[s]=r;
if (tmp[s]!=-1&&tmp[r]==-1)
{
tmp[r]=w;
}
if (countedge[u]>=3||countedge[v]>=3)
{
if (tmp[r]==-1){
tmp[r]=w;
}
}
vt[r].pb({s,w});
}
} dsu;
void dfs(int u)
{
for (auto v:vt[u])
{
parent[v.fi][0]=u;
mx[v.fi][0]=v.se;
for (int i=1;i<=18;i++)
{
mx[v.fi][i]=max(mx[v.fi][i-1],mx[parent[v.fi][i-1]][i-1]);
parent[v.fi][i]=parent[parent[v.fi][i-1]][i-1];
}
sz[v.fi]=sz[u]+1;
if (dsu.tmp[v.fi]!=-1)
{
}
else if (dsu.tmp[u]!=-1)
{
dsu.tmp[v.fi]=solvea(dsu.tmp[u],v.se);
}
dfs(v.fi);
}
}
void init(int N, int M,std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n=N;
m=M-1;
vector <iii> vta;
for (int i=1;i<=n;i++)
{
dsu.makeset(i);
}
for (int i=0;i<=m;i++)
{
ll u=U[i];
ll v=V[i];
u++;
v++;
ll w=W[i];
vta.pb({w,{u,v}});
}
sort (vta.begin(),vta.end());
for (auto v:vta)
{
dsu.Union(v.se.fi,v.se.se,v.fi);
}
ll ss=dsu.findset(1);
sz[ss]=0;
dfs(ss);
}
ii lca(int u,int v)
{
if (sz[u]>sz[v]){swap(u,v);}
ll pp=0;
for (int i=18;i>=0;i--)
{
if (sz[v]-mask(i)>=sz[u])
{
pp=max(pp,mx[v][i]);
v=parent[v][i];
}
}
if (u==v){return {u,pp};}
for (int i=18;i>=0;i--)
{
if (parent[u][i]!=parent[v][i])
{
pp=max({pp,mx[u][i],mx[v][i]});
u=parent[u][i];
v=parent[v][i];
}
}
if (u!=v)
{
pp=max({pp,mx[u][0],mx[v][0]});
u=parent[u][0];
v=parent[v][0];
}
return {u,pp};
}
int getMinimumFuelCapacity(int X, int Y) {
X++;
Y++;
ii aa=lca(X,Y);
if (dsu.tmp[X]==-1&&dsu.tmp[Y]==-1)
{
return -1;
}
aa.se=max(aa.se,solve(dsu.tmp[X],dsu.tmp[Y]));
return aa.se;
}
