#include "swap.h"
#include <iostream>
#include <vector>
using namespace std;
long long int f2[1000005],can=0,fa[1000005][21],deep[1000005],p[1000005],cnt,n,m,deg[1000005],u[1000005],v[1000005],w[1000005],f[1000005],ok[1000005],num[1000005],d[1000005];
int find(int x)
{
if(x==f2[x])return f2[x];
return f2[x]=find(f2[x]);
}
void qs(int s,int e)
{
if(s==e)return ;
long long int l=s,r=e,mid=w[(s+e)/2];
while(l<=r)
{
while(w[l]<mid)l++;
while(w[r]>mid)r--;
if(l<=r)
{
swap(w[l],w[r]);
swap(u[l],u[r]);
swap(v[l],v[r]);
l++;
r--;
}
}
if(r>s)qs(s,r);
if(e>l)qs(l,e);
}
void update(int x)
{
if(p[x]!=-1)return ;
//cout<<x<<" "<<ok[x]<<" "<<f[x]<<endl;
if(ok[x]==1)
{
p[x]=x;
return ;
}
update(f[x]);
p[x]=p[f[x]];
return ;
}
void update2(int x)
{
if(deep[x]!=0)return ;
if(f[x]==x)
{
deep[x]=1;
return ;
}
update2(f[x]);
deep[x]=deep[f[x]]+1;
return ;
}
void init(int N, int M,std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n=N;
m=M;
cnt=n-1;
for(int i=0;i<m;i++)
{
u[i]=U[i];
v[i]=V[i];
w[i]=W[i];
}
qs(0,m-1);
long long int ma=0;
for(int i=0;i<=1000000;i++)
{
f2[i]=i;
f[i]=i;
}
for(int i=0;i<m;i++)
{
long long int x=u[i],y=v[i];
deg[x]++;
deg[y]++;
long long int fx=find(x),fy=find(y);
//cout<<fx<<" "<<fy<<endl;
if(fx==fy)
{
if(ok[fx]==0)
{
can=1;
ok[fx]=1;
num[fx]=w[i];
}
}
else
{
if(ok[fx]==1 || ok[fy]==1 || deg[x]>=3 || deg[y]>=3)
{
cnt++;
//cout<<cnt<<" "<<x<<" "<<y<<endl;
can=1;
f[fx]=cnt;
f[fy]=cnt;
f2[fx]=cnt;
f2[fy]=cnt;
ok[cnt]=1;
num[cnt]=w[i];
}
else
{
f[fy]=fx;
f2[fy]=fx;
}
}
}
if(can==0)return ;
for(int i=0;i<=cnt;i++)
{
p[i]=-1;
}
for(int i=0;i<=cnt;i++)
{
if(p[i]==-1)update(i);
//cout<<i<<" "<<p[i]<<endl;
//cout<<i<<" "<<f[i]<<endl;
}
for(int i=0;i<=cnt;i++)
{
if(deep[i]==0)update2(i);
}
for(int i=0;i<=cnt;i++)
{
fa[i][0]=f[p[i]];
if(f[p[i]]==p[i])fa[i][0]=-1;
}
for(int i=1;i<=20;i++)
{
for(int j=0;j<=cnt;j++)
{
if(fa[j][i-1]==-1)continue;
fa[j][i]=fa[fa[j][i-1]][i-1];
}
}
return ;
}
int lca(int x,int y)
{
if(deep[x]<deep[y])swap(x,y);
//cout<<x<<" "<<y<<" "<<deep[x]<<" "<<deep[y]<<endl;
int tmp=deep[x]-deep[y];
int pp=0;
while(tmp>0)
{
if(tmp%2==1)x=fa[x][pp];
tmp/=2;
pp++;
}
if(x==y)return num[x];
for(int i=20;i>=0;i--)
{
if(fa[x][i]!=fa[y][i] && fa[x][i]!=-1)
{
x=fa[x][i];
y=fa[y][i];
}
}
return num[f[x]];
}
int getMinimumFuelCapacity(int X, int Y) {
if(can==0)return -1;
int x=p[X],y=p[Y];
//cout<<" "<<x<<" "<<y<<endl;
int ans=lca(x,y);
if(ans==0)return -1;
return ans;
}
