#include"swap.h"
#include<bits/stdc++.h>
using namespace std;
int getlog(long long n) { return 63-__builtin_clzll(n); }
const int MAXN=4e5+5;
struct edge { int l,r,v; };
bool comp(edge a,edge b) { return a.v<b.v; }
int dsu[MAXN],F[MAXN],sp[MAXN][20],pos[MAXN],dis[MAXN],N,rt;
vector<int> vi[MAXN],ds[MAXN];
edge E[MAXN];
pair<int,int> chain[MAXN];
bool del[MAXN];
int root(int i)
{
if(!dsu[i]) return i;
return dsu[i]=root(dsu[i]);
}
void merge(int i,int j,int k,int p)
{
int a=i,b=j;
if((i=root(i))==(j=root(j)))
{
del[i]=true;
for(auto v:vi[i]) F[v]=k;
vi[i].clear();
return ;
}
if(vi[i].size()<vi[j].size()) swap(i,j),swap(a,b);
if(a==chain[i].first) swap(chain[i].first,chain[i].second);
if(b==chain[j].second) swap(chain[j].first,chain[j].second);
for(auto v:vi[j]) vi[i].push_back(v);
dsu[j]=i,del[i]|=del[j]|(!(a==chain[i].second&&chain[j].first==b));
if(del[i])
{
for(auto v:vi[i]) F[v]=k;
vi[i].clear();
}
else chain[i].second=chain[j].second;
ds[p].push_back(pos[i]),ds[p].push_back(pos[j]),pos[i]=rt=p;
}
void dfs(int i,int pre)
{
sp[i][0]=pre;
for(int j=1;j<=19;j++) sp[i][j]=sp[sp[i][j-1]][j-1];
for(auto v:ds[i])
{
dis[v]=dis[i]+1;
dfs(v,i);
}
}
int lca(int a,int b)
{
int x=dis[a],y=dis[b],m=min(x,y);
for(int i=19;i+1;i--)
{
if((x-m)&(1<<i)) a=sp[a][i];
if((y-m)&(1<<i)) b=sp[b][i];
}
if(a==b) return a;
for(int i=19;i+1;i--) if(sp[a][i]!=sp[b][i]) a=sp[a][i],b=sp[b][i];
return sp[a][0];
}
void init(int n,int m,vector<int> U,vector<int> V,vector<int> W)
{
N=n;
for(int i=1;i<=n;i++) vi[i].push_back(i),chain[i]={i,i},pos[i]=i;
for(int i=1;i<=m;i++) E[i]={U[i-1]+1,V[i-1]+1,W[i-1]};
sort(E+1,E+m+1,comp);
for(int i=1;i<=m;i++) merge(E[i].l,E[i].r,i,i+n);
dfs(rt,rt);
}
int getMinimumFuelCapacity(int x,int y)
{
x++,y++;
if(!F[x]&&!F[y]) return -1;
return E[max(min(F[x],F[y]),lca(x,y)-N)].v;
}
