#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
const int N=100'000,LG=16;
int cost[2*N],t[2*N],tt[2*N][LG+1],cnt_edges[N],size,tin[2*N],tout[2*N],l_child[2*N],r_child[2*N];
int root(int x)
{
if(t[x]!=x)
{
t[x]=root(t[x]);
}
return t[x];
}
void unite(int x,int y,int c)
{
bool ok=(++cnt_edges[x]>=3 || ++cnt_edges[y]>=3);
x=root(x);
y=root(y);
if(x!=y)
{
tt[x][0]=t[x]=size;
l_child[size]=x;
tt[y][0]=t[y]=size;
r_child[size]=y;
if(ok || cost[x]>0 || cost[y]>0)
{
cost[size]=c;
}
tt[size][0]=t[size]=size;
size++;
}
else if(!cost[x])
{
cost[x]=c;
}
}
void dfs(int nod,int n)
{
static int timp=0;
tin[nod]=++timp;
if(nod>=n)
{
dfs(l_child[nod],n);
dfs(r_child[nod],n);
}
tout[nod]=timp;
}
void init(int n, int m,std::vector<int> x, std::vector<int> y, std::vector<int> w)
{
vector<int>ord(m);
iota(all(ord) , 0);
sort(all(ord) , [&](int x,int y){
return w[x]<w[y];
});
for(int i=0;i<n;i++)
{
tt[i][0]=t[i]=i;
}
size=n;
for(int i=0;i<m;i++)
{
unite(x[ord[i]] , y[ord[i]] , w[ord[i]]);
}
for(int i=1;i<=LG;i++)
{
for(int j=0;j<size;j++)
{
tt[j][i]=tt[tt[j][i-1]][i-1];
}
}
for(int i=size-1;i>=0;i--)
{
if(!tin[i])
{
dfs(i,n);
}
}
}
bool is_parent(int x,int y)
{
return tin[x]<=tin[y] && tout[y]<=tout[x];
}
int lca(int x,int y)
{
if(is_parent(x,y))
{
return x;
}
if(is_parent(y,x))
{
return y;
}
for(int i=LG;i>=0;i--)
{
if(!is_parent(tt[x][i],y))
{
x=tt[x][i];
}
}
return tt[x][0];
}
int getMinimumFuelCapacity(int x, int y)
{
if(root(x)!=root(y) || cost[root(x)]==0)
{
return -1;
}
int l=lca(x,y);
if(cost[l]>0)
{
return cost[l];
}
for(int i=LG;i>=0;i--)
{
if(cost[tt[l][i]]==0)
{
l=tt[l][i];
}
}
return cost[tt[l][0]];
}
/*
5 6
0 1 4
*/
