#include<bits/stdc++.h>
using namespace std;
struct graph {
int n, nlog;
vector<vector<pair<int,int>>> g;
vector<vector<int>> pr;
vector<vector<int>> val;
vector<int> pos;
vector<int> end;
graph() {
}
void resize(int n) {
g.resize(n);
pos.resize(n);
end.resize(n);
nlog = 0;
while (1 << nlog <= n) nlog++;
pr.resize(n, vector<int> (nlog));
val.resize(n, vector<int> (nlog));
}
void add(int u, int v, int w) {
g[u].emplace_back(v, w);
g[v].emplace_back(u, w);
}
void dfs(int v, int p = 0) {
static int count = -1;
pos[v] = ++count;
pr[v][0] = p;
for (int i = 1; i < nlog; i++) {
pr[v][i] = pr[pr[v][i-1]][i-1];
val[v][i] = max(val[v][i-1], val[pr[v][i-1]][i-1]);
}
for (auto&x : g[v]) {
int u = x.first;
if (u != p) {
val[u][0] = x.second;
dfs(u, v);
}
}
end[v] = count;
}
bool anc(int x, int y) {
return pos[x] <= pos[y] && end[y] <= end[x];
}
int lca(int x, int y) {
if (anc(x, y)) return x;
if (anc(y, x)) return y;
for (int i = nlog - 1; i >= 0; i--) {
if (pr[x][i] && !anc(pr[x][i], y)) x = pr[x][i];
}
return pr[x][0];
}
int get(int x, int y) {
int p = lca(x, y);
int ans = 0;
for (int i = nlog - 1; i >= 0; i--) {
if (pr[x][i] && anc(p, pr[x][i])) {
ans = max(ans, val[x][i]);
x = pr[x][i];
}
if (pr[y][i] && anc(p, pr[y][i])) {
ans = max(ans, val[y][i]);
y = pr[y][i];
}
}
return ans;
}
};
struct dsu {
vector<int> p;
int n;
dsu(int n) {
resize(n);
}
dsu() {
}
void resize(int _n) {
n = _n;
p = vector<int> (n, -1);
}
int get(int x) {
return p[x] < 0 ? x : p[x] = get(p[x]);
}
bool unite(int x, int y) {
x = get(x); y = get(y);
if (x != y) {
if (p[x] < p[y]) swap(x, y);
p[y] += p[x];
p[x] = y;
return true;
}
return false;
}
} d;
const int N = 1e5 + 3;
int n, m;
vector<tuple<int,int,int>> edges;
int deg[N];
int event[N];
vector<int> belong[N];
graph g;
void init(int _n, int _m, vector<int> u, vector<int> v, vector<int> w) {
n = _n;
m = _m;
for (int i = 0; i < m; i++) edges.emplace_back(w[i], u[i], v[i]);
sort(edges.begin(), edges.end());
d.resize(n);
g.resize(n);
for (int i = 0; i < n; i++) belong[i] = {i};
for (auto&x : edges) {
deg[get<1>(x)]++;
deg[get<2>(x)]++;
int u = d.get(get<1>(x)), v = d.get(get<2>(x));
bool to = (deg[get<1>(x)] >= 3 || deg[get<2>(x)] >= 3);
if (u == v) {
if (!event[u]) {
for (auto&y : belong[u]) event[y] = get<0> (x);
belong[u].clear();
}
}
else {
d.unite(u, v);
g.add(get<1>(x), get<2>(x), get<0>(x));
if (!event[u] && !event[v]) {
if (belong[u].size() < belong[v].size()) swap(u, v);
for (auto&x : belong[v]) belong[u].push_back(x);
belong[v].clear();
if (to) {
for (auto&y : belong[u]) event[y] = get<0>(x);
belong[u].clear();
}
else {
if (u != d.get(u)) swap(belong[u], belong[v]);
}
}
else {
for (auto&y : belong[u]) event[y] = get<0>(x);
belong[u].clear();
for (auto&y : belong[v]) event[y] = get<0>(x);
belong[v].clear();
}
}
}
g.dfs(0, 0);
}
int getMinimumFuelCapacity(int x, int y) {
if (!event[x] || !event[y]) return -1;
return max({event[x], event[y], g.get(x, y)});
}
