#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
const int M = 2e5;
const int inf = 2e9;
int id[M],deg[N];
struct nodedata{
int parent,active;
};
vector <nodedata> nodes;///parent,active
vector <int> e[2*N - 1];
int p2[2*N - 1][20];
int dpth[2*N - 1];
struct dsu{
int id,parent,active,sz;
};
dsu v[N];
int leader(int node){
if(node == v[node].parent)return node;
int l = leader(v[node].parent);
v[node].parent = l;
return v[node].parent;
}
void connect(int a,int b,int w){
deg[a]++;deg[b]++;
int active = inf;
if(deg[a] >= 3 || deg[b] >= 3)active = min(active,w);
a = leader(a);b = leader(b);
if(a == b){
nodes[v[a].id].active = min(nodes[v[a].id].active,w);
v[a].active = min(v[a].active,w);
}else{
nodes[v[a].id].parent = nodes.size();
nodes[v[b].id].parent = nodes.size();
if(v[a].sz < v[b].sz)swap(a,b);
v[b].parent = a;
v[a].sz+=v[b].sz;
v[a].id = nodes.size();
nodes.push_back({-1,active});
v[a].active = min(v[b].active,v[a].active);
}
}
void dfs(int node,int p = -1,int d = 0){
dpth[node] = d;
p2[node][0] = p;
for(auto i:e[node]){
if(i == p)continue;
dfs(i,node,d + 1);
}
}
void init(int n, int m,vector<int> u,vector<int> u2,vector<int> w) {
int i,j;
for(i = 0;i < m;i++)id[i] = i;
for(i = 0;i < n;i++){
nodes.push_back({-1,inf});
v[i] = {i,i,inf,1};
}
sort(id,id + m,[&](int a,int b){
return w[a] < w[b];
});
for(i = 0;i < m;i++){
///connect u[id[i]] with v[id[i]]
connect(u[id[i]],u2[id[i]],w[id[i]]);
//cout<<u[id[i]]<<' '<<u2[id[i]]<<'\n';
}
int cnt = 0;
for(auto i:nodes){
if(i.parent != -1){
e[i.parent].push_back(cnt);
}
cnt++;
}
dfs(nodes.size() - 1,-1);
for(j = 1;j < 20;j++){
for(i = 0;i < 2*n - 1;i++){
if(p2[i][j - 1] == -1)p2[i][j] = -1;
else p2[i][j] = p2[p2[i][j - 1]][j - 1];
}
}
/*for(i = 0;i < 2*n - 1;i++){
for(j = 0;j < 20;j++)cout<<p2[i][j]<<' ';
cout<<'\n';
}
for(i = 0;i < 2*n - 1;i++){
cout<<p2[i][0]<<' '<<dpth[i]<<' '<<nodes[i].active<<' '<<i<<'\n';
}*/
}
int getMinimumFuelCapacity(int x, int y) {
if(dpth[x] < dpth[y])swap(x,y);
for(int i = 19;i >= 0;i--){
if(dpth[x] - (1<<i) >= dpth[y]){
x = p2[x][i];
}
}
for(int i = 19;i >= 0;i--){
if(p2[x][i] != p2[y][i]){
x = p2[x][i];y = p2[y][i];
}
}
if(x != y)x = p2[x][0];
//cout<<x<<'\n';
for(int i = 19;i >= 0;i--){
//cout<<x<<' '<<p2[x][i]<<'\n';
if(p2[x][i] != -1 && nodes[p2[x][i]].active == inf){
x = p2[x][i];
}
}
if(nodes[x].active == inf){
x = p2[x][0];
}
return (x==-1?-1:nodes[x].active);
}
/**
5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
3
1 2
2 4
0 1
3 2
0 1 5
0 2 5
1
1 2
**/
