#include "swap.h"
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
struct node
{
ll u1,u2,w;
} a[200009];
ll n,p[300009],c[100009],ans[300009];
ll dp[300009][20],h[300009],logn;
vector<vector<ll> >v;
bool cmp(const node&xo,const node&yo)
{
return xo.w<yo.w;
}
ll gp(ll z)
{
if(p[z]==z)
return z;
return p[z]=gp(p[z]);
}
void mrg(ll x,ll y,ll z)
{
c[x]++,c[y]++;
bool is = (c[x]>2||c[y]>2);
x=gp(x),y=gp(y);
n++;
p[x]=p[y]=p[n]=n;
if(x==y)
{
is=1;
v[n].push_back(x);
}
else
{
v[n].push_back(x);
v[n].push_back(y);
}
if(ans[x]<2e9||ans[y]<2e9)
is=1;
if(is)
ans[n]=z;
else
ans[n]=2e9;
}
void dfs(ll d,ll pp)
{
dp[d][0]=pp;
h[d]=h[pp]+1;
ans[d]=min(ans[d],ans[pp]);
for(auto z:v[d])
dfs(z,d);
if(ans[d]==2e9)
ans[d]=-1;
}
void init(int N,int M,vector<int> U,vector<int> V,vector<int> W)
{
v.resize(N+M+9);
for(ll i=0; i<M; i++)
{
a[i].u1=U[i];
a[i].u2=V[i];
a[i].w =W[i];
}
sort(a,a+M,cmp);
n=N-1;
for(ll i=0; i<N; i++)
p[i]=i,ans[i]=2e9;
for(ll i=0; i<M; i++)
mrg(a[i].u1,a[i].u2,a[i].w);
logn=log2(n)+1;
ll root=gp(0);
dfs(root,root);
for(ll j=1; j<=logn; j++)
for(ll i=0; i<=n; i++)
dp[i][j]=dp[ dp[i][j-1] ][j-1];
}
int getMinimumFuelCapacity(int x, int y)
{
ll lca;
if(h[x]<h[y])
swap(x,y);
ll dif=h[x]-h[y];
for(ll i=logn; i>=0; i--)
if(dif&(1<<i))
x=dp[x][i];
for(ll i=logn; i>=0; i--)
if(dp[x][i]!=dp[y][i])
x=dp[x][i],y=dp[y][i];
if(x==y)
lca=x;
else
lca=dp[x][0];
return ans[lca];
}
