#include "swap.h"
#include "bits/stdc++.h"
#define FOR(i,a,b)for(int i=(a);i<(b);i++)
#define F0R(i,a)FOR(i,0,a)
using namespace std;
const int mxn=1e5+20,mxm=2e5+20,inf=0x3f3f3f3f;
int deg[mxm];
struct{
vector<pair<int,int>>vp[mxn];
vector<int>cmp[mxn];
int ar[mxn],when[mxn];
void init(int n){
iota(ar,ar+n,0);
F0R(i,n)cmp[i].push_back(i);
memset(when,0x3f,sizeof(when));
}
void unite(array<int,3>&eg){
deg[eg[1]]++,deg[eg[2]]++;
int u=ar[eg[1]],v=ar[eg[2]];
if(u==v){
when[u]=min(when[u],eg[0]);
return;
}
if(cmp[u].size()<cmp[v].size())swap(u,v);
for(int i:cmp[v]){
cmp[u].push_back(i);
ar[i]=u;
vp[i].emplace_back(u,eg[0]);
}
cmp[v].clear();
if(when[v]!=inf)when[u]=min(when[u],eg[0]);
if(deg[eg[1]]>=3 or deg[eg[2]]>=3)when[u]=min(when[u],eg[0]);
}
}dsu;
void init(int N,int M,vector<int>U,vector<int>V,vector<int>W) {
dsu.init(N);
vector<array<int,3>>v;
F0R(i,M)v.push_back({W[i],U[i],V[i]});
sort(begin(v),end(v));
for(auto&eg:v)dsu.unite(eg);
}
int getMinimumFuelCapacity(int X,int Y) {
if(dsu.when[dsu.ar[X]]==inf)return -1;
int u=X,v=Y,a=0,b=0,ans=0;
while(u!=v or dsu.when[u]==inf){
if(a==dsu.vp[X].size() or (b!=dsu.vp[Y].size() and dsu.vp[X][a].second>dsu.vp[Y][b].second))
v=dsu.vp[Y][b].first,ans=dsu.vp[Y][b++].second;
else u=dsu.vp[X][a].first,ans=dsu.vp[X][a++].second;
}
return max(ans,dsu.when[u]);
}
