#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <numeric>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define ll long long
#define ull unsigned long long
#define f first
#define s second
#define PF push_front
#define PB push_back
#define MP make_pair
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define max(a, b) ((a > b)? a : b)
#define min(a, b) ((a < b)? a : b)
#define max3(a, b, c) max(max(a, b), c)
#define min3(a, b, c) min(min(a, b), c)
const int N = 1e5 + 5;
const int M = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll int INF = 1e18;
struct DSU{
vector<int> parent, edge_cnt;
vector<bool> swappable;
DSU(int n){
parent = vector<int>(n+1);
iota(all(parent), 0);
edge_cnt = vector<int>(n+1, 0);
swappable = vector<bool>(n+1, false);
}
int find_parent(int p){
return (parent[p] == p)? p : parent[p] = find_parent(parent[p]);
}
void merge(int a, int b){
int pa = find_parent(a);
int pb = find_parent(b);
edge_cnt[a]++;
edge_cnt[b]++;
// Degree >= 3
if(edge_cnt[a] >= 3) swappable[pa] = true;
if(edge_cnt[b] >= 3) swappable[pb] = true;
// Contains cycle
if(pa == pb) swappable[pb] = true;
parent[pa] = pb;
if(swappable[pa]) swappable[pb] = true;
}
bool is_same_union(int a, int b){
int pa = find_parent(a);
int pb = find_parent(b);
return (pa == pb);
}
bool check(int a, int b){
int pa = find_parent(a);
int pb = find_parent(b);
return (pa == pb && swappable[pa]);
}
};
int _n, _m;
vector<tuple<int, int, int>> edge;
vector<vector<int>> adj, par;
vector<int> tin, tout, val;
vector<bool> node_swappable;
DSU dsu(0);
int timer = 0;
void tour(int cur, int prev = -1){
tin[cur] = timer++;
for(int child : adj[cur]){
if(child == prev) continue;
par[child][0] = cur;
tour(child, cur);
}
tout[cur] = timer++;
}
bool isAnc(int child, int anc){
return (tin[anc] <= tin[child] && tout[anc] >= tout[child]);
}
int get_swaplca(int a, int b){
if(isAnc(a, b)) swap(a, b);
int lca = a, cur = b;
for(int i = 19; i >= 0; i--){
int next_cur = par[cur][i];
if(isAnc(a, next_cur) && node_swappable[next_cur]){
lca = next_cur;
}else {
cur = next_cur;
}
}
return lca;
}
void init(int n, int m, vector<int> u, vector<int> v, vector<int> w){
_n = n;
_m = m;
edge.clear();
adj.clear(); adj.resize(n+m);
par.resize(n+m, vector<int>(20));
for(int i = 0; i < m; i++) edge.PB({w[i], u[i], v[i]});
sort(all(edge));
vector<int> index(n);
iota(all(index), 0);
tin.resize(n+m);
tout.resize(n+m);
val.resize(n+m);
node_swappable.resize(n+m, false);
int index_counter = n;
dsu = DSU(n);
for(int i = 0; i < m; i++){
auto [w, u, v] = edge[i];
int pu = dsu.find_parent(u);
int pv = dsu.find_parent(v);
dsu.merge(u, v);
int rep = dsu.find_parent(u);
if(pu == pv){
// Same union
adj[index_counter].PB(index[rep]);
adj[index[rep]].PB(index_counter);
}else {
// Merge union
adj[index_counter].PB(index[pu]);
adj[index_counter].PB(index[pv]);
adj[index[pu]].PB(index_counter);
adj[index[pv]].PB(index_counter);
}
val[index_counter] = w;
node_swappable[index_counter] = dsu.swappable[rep];
index[rep] = index_counter++;
}
par[index_counter-1][0] = index_counter-1;
tour(index_counter-1);
for(int i = 1; i < 20; i++){
for(int j = 0; j < index_counter; j++){
par[j][i] = par[par[j][i-1]][i-1];
}
}
}
// Full solution
int getMinimumFuelCapacity(int x, int y){
int lca = get_swaplca(x, y);
if(lca < _n) return -1;
return val[lca];
}
