#include <bits/stdc++.h>
using namespace std;
#include "swap.h"
//#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
vector <int> waiting[200005];
int par[200005], val[200005], deg[200005], good[200005], up[20][200005], dep[200005];
int cnt = 1;
pi adj[200005];
int getr(int x){return par[x] == x ? x : par[x] = getr(par[x]);}
void merge(int a, int b, int c){
a = getr(a); b = getr(b);
if(a == b)return;
par[a] = par[b] = up[0][a] = up[0][b] = par[cnt];
val[cnt] = c;
adj[cnt] = {a, b};
//good[cnt] = 1;
cnt++;
}
int par2[200005];
int g2(int x){return par2[x] == x ? x : par2[x] = g2(par2[x]);}
void m2(int a, int b){par2[g2(b)] = g2(a);}
void dfs(int x, int d){
//cout << x << '\n';
dep[x] = d;
if(adj[x].fi == adj[x].se)return;
dfs(adj[x].fi, d + 1);
dfs(adj[x].se, d + 1);
}
int lca(int u, int v){
if(dep[u] > dep[v])swap(u, v);
int df = dep[v] -dep[u];
for(int i = 0; i <= 19; i++)if(df >> i & 1)v = up[i][v];
if(u ==v )return u;
for(int i = 19; i >=0 ; i--)if(up[i][u] != up[i][v])u = up[i][u], v = up[i][v];
return up[0][u];
}
void init(int N, int M,
std::vector<int> U, std::vector<int> V, std::vector<int> W) {
vector <pii> bb;
cnt = N;
for(int i = 0; i < 2 * N; i++)par[i] = par2[i] = i;
for(int i = 0; i < M; i++)bb.push_back({W[i], {U[i], V[i]}});
sort(bb.begin(), bb.end());
for(auto i : bb){
int a = i.se.fi, b = i.se.se, w = i.fi;
if(g2(a) == g2(b)){
good[getr(a)] = 1;
good[getr(b)] = 1;
queue <int> q;
q.push(a);
q.push(b);
merge(a, b, w);
while(!q.empty()){
int x = q.front(); q.pop();
vector <int> aa = waiting[x];
waiting[x].clear();
for(auto j : aa){
if(getr(j) != getr(x)){
merge(x, j, w);
q.push(j);
}
}
}
}
else{
m2(a, b);
//if(getr(a) != a || getr(b) != b)merge(a, b, w);
if(getr(a) != a || getr(b) != b){
queue <int> q;
q.push(a);
q.push(b);
merge(a, b, w);
while(!q.empty()){
int x = q.front(); q.pop();
vector <int> aa = waiting[x];
waiting[x].clear();
for(auto j : aa){
if(getr(j) != getr(x)){
merge(x, j, w);
q.push(j);
}
}
}
}
else{
deg[a]++; deg[b]++;
if(max(deg[a], deg[b]) >= 3){
good[getr(a)] = good[getr(b)] = 1;
queue <int> q;
q.push(a);
q.push(b);
merge(a, b, w);
while(!q.empty()){
int x = q.front(); q.pop();
vector <int> aa = waiting[x];
waiting[x].clear();
for(auto j : aa){
if(getr(j) != getr(x)){
merge(x, j, w);
q.push(j);
}
}
}
}
else waiting[a].push_back(b), waiting[b].push_back(a);
}
}
}
for(int i = cnt - 1; i >= N; i--)if(!dep[i])dfs(i, 1);
for(int i = 1; i <= 19; i++)for(int j = 0; j < 2 * N; j++)up[i][j] = up[i - 1][up[i - 1][j]];
}
int getMinimumFuelCapacity(int X, int Y) {
if(getr(X) != getr(Y))return -1;
//cout << lca(X, Y) << ' ';
return val[lca(X, Y)];
}
