#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
int const LOG=20;
int const MAX=2e5+5;
struct edge{
int u,v,w;
bool operator<(edge ot){
return w<ot.w;
}
}edges[MAX];
int val[MAX];
pair<int,int>lant[MAX];
int lift[MAX][LOG];
vector<int>sons[MAX];
int h[MAX];
bool find_link(multiset<int>&ms,int u,int v){
if(ms.find(u)==ms.end() || ms.find(v)==ms.end())
return 0;
ms.erase(ms.find(u));
ms.erase(ms.find(v));
return 1;
}
struct DSU{
int total;
int tata[MAX];
void initializare(int n){
total=n;
int i;
for(i=0;i<total;++i){
tata[i]=i;
lant[i]={i,i};
}
}
int root(int nod){
if(tata[nod]==nod)
return nod;
return tata[nod]=root(tata[nod]);
}
void uneste(int u,int v,int w){
int ru=root(u);
int rv=root(v);
if(ru==rv){
if(!val[ru]){
val[ru]=w;
lant[ru]={-1,-1};
}
}
else{
tata[ru]=total;
tata[rv]=total;
tata[total]=total;
lift[ru][0]=total;
lift[rv][0]=total;
sons[total]={ru,rv};
if(lant[ru].first!=-1 && lant[rv].first!=-1){
multiset<int>ms;
ms.insert(lant[ru].first);
ms.insert(lant[ru].second);
ms.insert(lant[rv].first);
ms.insert(lant[rv].second);
if(find_link(ms,u,v))
lant[total]={*ms.begin(),*next(ms.begin())};
else{
lant[total]={-1,-1};
val[total]=w;
}
}
else{
lant[total]={-1,-1};
val[total]=w;
}
++total;
}
}
}dsu;
void dfs(int nod){
for(auto fiu : sons[nod]){
h[fiu]=h[nod]+1;
dfs(fiu);
}
}
void init(int N,int M,vector<int>U,vector<int>V,vector<int>W){
int i;
for(i=0;i<M;++i)
edges[i]={U[i],V[i],W[i]};
sort(edges,edges+M);
dsu.initializare(N);
for(i=0;i<M;++i)
dsu.uneste(edges[i].u,edges[i].v,edges[i].w);
dfs(dsu.total-1);
lift[dsu.total-1][0]=dsu.total-1;
int j;
for(j=1;j<LOG;++j)
for(i=0;i<dsu.total;++i)
lift[i][j]=lift[lift[i][j-1]][j-1];
if(!val[dsu.total-1]){
for(i=0;i<dsu.total;++i)
val[i]=-1;
}
else{
for(i=dsu.total-2;i>=0;--i)
if(!val[i])
val[i]=val[lift[i][0]];
}
}
int lca(int u,int v){
if(h[u]<h[v])
swap(u,v);
int dif=h[u]-h[v];
int i;
for(i=0;i<LOG;++i)
if(dif&(1<<i))
u=lift[u][i];
if(u==v)
return u;
for(i=LOG-1;i>=0;--i)
if(lift[u][i]!=lift[v][i]){
u=lift[u][i];
v=lift[v][i];
}
return lift[u][0];
}
int getMinimumFuelCapacity(int X, int Y) {
return val[lca(X,Y)];
}
