#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int p[300005], f[300005], ff[300005], d[300005], dd[300005], b[300005], l[300005][19], da[300005];
vector<int> g[300005];
int Find(int x) {
if (x == p[x]) return x;
return p[x] = Find(p[x]);
}
void Merge(int x, int y, int i) {
d[x]++; d[y]++;
int fl = 0;
if (d[x] >= 3 || d[y] >= 3) fl = 1;
x = Find(x);
y = Find(y);
if (x == y) fl = 1;
fl |= f[x] | f[y];
f[i] = fl;
p[x] = p[y] = i;
g[i].push_back(x);
if (x != y) g[i].push_back(y);
dd[x] = dd[y] = 1;
}
void dfs(int x, int p, int h) {
l[x][0] = p;
if (f[x] == 1) h = b[x];
ff[x] = h;
for (int w : g[x]) {
da[w] = da[x] + 1;
dfs(w, x, h);
}
}
int lca(int x, int y) {
if (da[x] < da[y]) swap(x, y);
int k = da[x] - da[y];
for (int i = 0; i < 19; i++) {
if (k & (1 << i)) {
x = l[x][i];
}
}
if (x == y) return x;
for (int i = 18; i >= 0; i--) {
if (l[x][i] != l[y][i]) {
x = l[x][i];
y = l[y][i];
}
}
return l[x][0];
}
void init(int n, int m, vector<int> u, vector<int> v, vector<int> w) {
vector<pair<int, pair<int, int>>> a;
for (int i = 0; i < m; i++) {
a.push_back({w[i], {u[i], v[i]}});
}
for (int i = 0; i < n + m; i++) p[i] = i;
sort(a.begin(), a.end());
for (int i = 0; i < m; i++) {
Merge(a[i].second.first, a[i].second.second, i + n);
b[i + n] = a[i].first;
}
for (int i = 0; i < n + m; i++) {
if (dd[i] == 0) {
dfs(i, n + m, 0);
}
}
for (int i = 0; i <= 18; i++) l[n + m][i] = n + m;
for (int i = 1; i <= 18; i++) {
for (int j = 0; j < n + m; j++) {
l[j][i] = l[l[j][i - 1]][i - 1];
}
}
}
int getMinimumFuelCapacity(int x, int y) {
int h = ff[lca(x, y)];
if (h == 0) return -1;
return h;
}
