#include<bits/stdc++.h>
#include "swap.h"
#define st first
#define nd second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define pp pop_back
#define mp make_pair
using namespace std;
using pii = pair<int, int>;
using ll = long long;
using vi = vector<int>;
using vii = vector<pii>;
void debug(){cerr<<"\n";}
template<typename H, typename... T>
void debug(H h, T... t){
cerr<<h;
if(sizeof...(t)){
cerr<<", ";
}
debug(t...);
}
#define deb(x...) cerr<<#x<<" = ";debug(x);
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const int K=18, N=3e5+5;
int r[N], par[K][N], tim[N], czy[N], deg[N], nxt[N], dep[N];
int find(int v){
if(r[v]==v)return v;
return r[v]=find(r[v]);
}
void init(int n, int m, std::vector<int> uu, std::vector<int> vv, std::vector<int> ww) {
vector<pair<int, pii> > edg;
for(int i=0; i<m; i++){
edg.eb(ww[i], mp(uu[i], vv[i]));
}
sort(all(edg));
for(int i=0; i<N; i++){
r[i]=i;
}
int wsk=n;
for(int ii=0; ii<m; ii++){
int u=edg[ii].nd.st, v=edg[ii].nd.nd, w=edg[ii].st;
deg[u]++;
deg[v]++;
bool b=(deg[u]>=3||deg[v]>=3);
u=find(u);
v=find(v);
if(u==v && !czy[u]){
par[0][u]=r[u]=wsk;
tim[wsk]=w;
czy[wsk]=1;
wsk++;
}
if(u!=v){
par[0][u]=r[u]=wsk;
par[0][v]=r[v]=wsk;
tim[wsk]=w;
czy[wsk]=(b||czy[u]||czy[v]);
wsk++;
}
}
par[0][wsk-1]=wsk-1;
for(int k=1; k<K; k++){
for(int i=0; i<wsk; i++){
par[k][i]=par[k-1][par[k-1][i]];
}
}
for(int i=wsk-1; i>=0; i--){
if(czy[i])nxt[i]=tim[i];
else{
if(par[0][i]==i)nxt[i]=1e9+5;
else nxt[i]=nxt[par[0][i]];
}
if(par[0][i]!=i)dep[i]=dep[par[0][i]]+1;
}
for(int i=0; i<wsk; i++){
//deb(i, par[0][i], czy[i], tim[i], nxt[i], dep[i]);
}
}
int lca(int u, int v){
if(dep[u]>dep[v])swap(u, v);
for(int i=K-1; i>=0; i--){
if(dep[u]+(1<<i)<=dep[v])v=par[i][v];
}
if(u==v)return u;
for(int i=K-1; i>=0; i--){
if(par[i][v]!=par[i][u]){
v=par[i][v];
u=par[i][u];
}
}
return par[0][u];
}
int getMinimumFuelCapacity(int X, int Y) {
if(X==Y)return 0;
int Z=lca(X, Y);
if(nxt[Z]==1e9+5)return -1;
else return nxt[Z];
}
