#include "swap.h"
#include<bits/stdc++.h>
#define int long long
#define mp make_pair
#define pb push_back
#define f0r(i,n) for(signed i = 0; i<n; i++)
#define FOR(i, k, n) for(signed i = k; i<n; i++)
#define vi vector<int>
#define vpii vector<pair<int,int>>
#define pii pair<int,int>
#define vb vector<bool>
#define mii map<int,int>
#define vvi vector<vector<int>>
#define vout(v) for(auto u : v)cout<<u<<' '; cout<<endl;
#define dout(a) cout<<a<<' '<<#a<<endl;
#define dout2(a,b) cout<<a<<' '<<#a<<' '<<b<<' '<<#b<<endl;
using namespace std;
struct edge{
int u, v, w;
};
vector<vpii> adj;
int n,m;
vector<vi>edges;
struct DSU{
int n; vi par, sz, hasthree, hascyc, rep;
vi treepar, treesz, treea, treeb, weight, dep;
vvi adj;
int node_count;
int m, lg; vvi jmp;
DSU(){
}
DSU(int N){
n = N; node_count = n;
par.resize(n); sz.resize(n); hasthree.resize(n); hascyc.resize(n);
f0r(i,n){
par[i] = i; sz[i] = 1; hasthree[i] = 0; hascyc[i] = 0; rep.pb(i);
treepar.pb(-1); treesz.pb(1); treea.pb(0); treeb.pb(0); weight.pb(0);
}
}
int find(int x){
while(x != par[x])x = par[x];
return x;
}
void unite(int a, int b, int w){
// dout2(a,b);
a = find(a); b = find(b);
if(a == b){
// dout(rep[a]);
treepar[rep[a]] = node_count;
treepar.pb(-1);
treesz.pb(sz[a]);
treea.pb(treea[a]);
weight.pb(w);
treeb.pb(1);
rep[a] = node_count;
node_count++;
hascyc[a] = 1;
// vout(treepar);
return;
}
if(sz[a] < sz[b])swap(a,b);
treepar[rep[a]] = node_count;
treepar[rep[b]] = node_count;
treepar.pb(-1);
treesz.pb(sz[a] + sz[b]);
treea.pb(hascyc[a] | hascyc[b]);
treeb.pb(hasthree[a] | hasthree[b]);
weight.pb(w);
rep[a] = node_count;
sz[a] += sz[b];
par[b] = a;
hascyc[a] |= hascyc[b];
hasthree[a] |= hasthree[b];
node_count++;
// vout(treepar);
}
void build_jmp(){
m = node_count;
jmp.resize(m);
lg = 0;
for(int i = 62; i>=0; i--){
if((1LL << i) & m){
lg = i; break;
}
}
lg++;
f0r(i,m){
jmp[i].resize(lg);
}
f0r(i,m){
jmp[i][0] = treepar[i];
}
// vout(treepar);
FOR(i, 1, lg){
f0r(j, m){
if(jmp[j][i-1] == -1)jmp[j][i] = -1;
else jmp[j][i] = jmp[jmp[j][i-1]][i-1];
}
}
adj.resize(m);
f0r(i,m){
if(treepar[i] != -1)adj[treepar[i]].pb(i);
}
dep.resize(m);
queue<int>q;
q.push(m-1);
while(!q.empty()){
int node = q.front(); q.pop();
for(auto u : adj[node]){
q.push(u);
dep[u] = dep[node] + 1;
}
}
}
int lca(int a, int b){
if(dep[a] > dep[b])swap(a,b);
int dif = dep[b] - dep[a];
f0r(i, lg){
if((1LL << i) & dif){
b = jmp[b][i];
}
}
for(int i = lg - 1; i>=0; i--){
if(jmp[a][i] != jmp[b][i]){
a = jmp[a][i]; b = jmp[b][i];
}
}
return treepar[a];
}
int firstcan(int x){
// dout(x);
if(treea[x] || treeb[x])return x;
for(int i = lg-1; i>=0; i--){
if(!(treea[jmp[x][i]] || treeb[jmp[x][i]])){
x = jmp[x][i];
}
}
if(x == m-1)return -1;
x = treepar[x];
return x;
}
};
vi dist;
int l2;
DSU d = DSU();
void init(signed N, signed M,
std::vector<signed> U, std::vector<signed> V, std::vector<signed> W) {
n = N; m = M;
adj.resize(N); dist.resize(n);
dist[0] = 4e18;
f0r(i, M){
edges.pb({W[i], U[i], V[i]});
adj[U[i]].pb(mp(V[i], W[i]));
adj[V[i]].pb(mp(U[i], W[i]));
dist[V[i]] = W[i];
}
sort(edges.begin(), edges.end());
d = DSU(n);
f0r(i, M){
d.unite(edges[i][1], edges[i][2], edges[i][0]);
}
d.build_jmp();
}
signed getMinimumFuelCapacity(signed X, signed Y) {
if(n <= 3)return -1;
// return 0;
int l = d.lca(X, Y);
int ans = d.firstcan(l);
if(ans == -1)return -1;
return d.weight[ans];
/*
vi deg(n);
DSU d = DSU(n);
f0r(i, m){
d.unite(edges[i][1], edges[i][2]);
deg[edges[i][1]]++;
deg[edges[i][2]]++;
int x = d.find(X);
int y = d.find(Y);
if(deg[edges[i][1]] == 3){
d.hasthree[d.find(edges[i][1])] = 1;
}
if(deg[edges[i][2]] == 3){
d.hasthree[d.find(edges[i][2])] = 1;
}
if(x == y && (d.hasthree[x] || d.hascyc[x])){
return edges[i][0];
}
}
return -1;
*/
}
