#include "swap.h"
#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pii pair<int, int>
const int mxN = 4e5 + 5;
using namespace std;
struct edge{
int u,v,w;
friend bool operator<(edge a, edge b){
return a.w < b.w;
}
};
vector<vector<pii>>v;
pii st[mxN][32];
bool swp[mxN];
int dsu[mxN],sz[mxN],h[mxN],deg[mxN],id[mxN];
int curid;
void dfs(int u,int p){
if(u != curid) h[u] = h[p] + 1;
for(auto x : v[u]) if(x.F != p) dfs(x.F,u);
}
void connect(int x,int y,int z,int val){
// cout<<x<<' '<<y<<' '<<z<<' '<<val<<'\n';
v[x].push_back({y,val});
v[y].push_back({x,val});
st[y][0] = {x,val};
if(z != y){
v[x].push_back({z,val});
v[z].push_back({x,val});
st[z][0] = {x,val};
}
}
int lca(int x,int y){
int val = 0;
if(h[x] > h[y]) swap(x,y);
// cout<<h[x]<<' '<<h[y]<<'\n';
for(int i = 20;i >= 0;i--){
int b = st[y][i].F;
if(h[b] >= h[x]) {
val = st[y][i].S;
y = b;
}
}
for(int i = 20;i >= 0;i--){
int a = st[x][i].F,b = st[y][i].F;
// cout<<a<<' '<<b<<'\n';
if(a != b || !(swp[a] || swp[b])){
val = max({val,st[x][i].S,st[y][i].S});
x = a;
y = b;
}
}
val = max(st[x][0].S,st[y][0].S);
// cout<<st[x][0].F<<'\n';
return val;
}
int find(int x){
return (dsu[x] == x ? x : dsu[x] = find(dsu[x]));
}
void merge(int a,int b,int val){
int fa = find(a),fb = find(b);
deg[a]++;
deg[b]++;
if(sz[a] < sz[b]){
swap(a,b);
swap(fa,fb);
}
if(fa != fb && sz[fa] == sz[fb]) sz[fa]++;
dsu[fb] = fa;
if(swp[fa] || swp[fb] || deg[a] >= 3 || deg[b] >= 3 || fa == fb) swp[fa] = 1;
connect(++curid,id[fa],id[fb],val);
id[fa] = curid;
swp[id[fa]] = swp[fa];
}
vector<edge>edges;
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
v.resize(2 * (N + M));
curid = N - 1;
for(int i = 0;i < M;i++){
edges.push_back({U[i],V[i],W[i]});
}
for(int i = 0;i <= N + M;i++) {
dsu[i] = i;
id[i] = i;
}
sort(edges.begin(),edges.end());
for(auto x : edges){
// cout<<x.u<<' '<<x.v<<' '<<x.w<<'\n';
merge(x.u,x.v,x.w);
// int fa = find(x.y);
// cout<<fa<<' '<<swp[fa]<<'\n';
}
st[curid][0] = {curid,0};
for(int pw = 1;pw <= 20;pw++){
for(int i = 0; i <= curid;i++){
st[i][pw] = {st[st[i][pw - 1].F][pw - 1].F, max(st[st[i][pw - 1].F][pw - 1].S,st[i][pw - 1].S)};
}
}
dfs(curid,curid);
}
int getMinimumFuelCapacity(int X, int Y) {
return ((find(X) != find(Y) || !swp[find(X)]) ? -1 : lca(X,Y));
}
