#include <bits/stdc++.h>
using namespace std;
#include "swap.h"
const int Z = 1e5, B = 18, INF = 2e9;
array<int, B> p[Z], q[Z], r[Z];
vector<int> e(Z, -1), d(Z);
vector<array<int, 2>> g[Z];
set<array<int, 2>> s[Z];
int find(int u) {
return e[u] < 0 ? u : e[u] = find(e[u]);
}
void dfs_0(int u) {
for(auto &[v, w] : g[u]) if(v != p[u][0]) {
p[v][0] = u, q[v][0] = w, d[v] = d[u] + 1;
dfs_0(v);
if(size(s[u]) < size(s[v]))
s[u].swap(s[v]);
for(auto &i : s[v])
if(s[u].find(i) == end(s[u]))
s[u].insert(i);
else
s[u].erase(i);
}
if(!empty(s[u])) r[u][0] = (*begin(s[u]))[0];
else r[u][0] = INF;
}
void dfs_1(int u) {
for(int i = 1; i < B; i++) {
p[u][i] = p[p[u][i-1]][i-1];
q[u][i] = max(q[u][i-1], q[p[u][i-1]][i-1]);
r[u][i] = min(r[u][i-1], r[p[u][i-1]][i-1]);
}
for(auto &[v, w] : g[u]) if(v != p[u][0])
dfs_1(v);
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
array<int, 3> h[M];
for(int i = 0; i < M; i++) {
h[i] = {W[i], U[i], V[i]};
}
sort(h, h+M);
for(int i = 0; i < M; i++) {
int u = find(h[i][1]), v = find(h[i][2]), w = h[i][0];
if(u == v)
for(int k : {1, 2})
s[h[i][k]].insert({w, i});
else {
if(e[u] > e[v]) swap(u, v);
e[u] += e[v], e[v] = u;
for(int k : {1, 2})
g[h[i][k]].push_back({h[i][3-k], w});
}
}
for(int &i : r[0]) i = INF;
dfs_0(0), dfs_1(0);
}
int getMinimumFuelCapacity(int X, int Y) {
int u = X, v = Y, qV = 0, rV = INF;
if(d[u] > d[v]) swap(u, v);
for(int i = 0; i < B; i++) {
if((d[v] - d[u]) & (1<<i)) {
qV = max(qV, q[v][i]);
rV = min(rV, r[v][i]);
v = p[v][i];
}
}
if(u != v) {
for(int i = B; --i; ) {
if(p[u][i] != p[v][i]) {
qV = max({qV, q[u][i], q[v][i]});
rV = min({rV, r[u][i], r[v][i]});
u = p[u][i];
v = p[v][i];
}
}
qV = max({qV, q[u][0], q[v][0]});
rV = min({rV, r[u][0], r[v][0]});
}
return rV == INF ? -1 : max(rV, qV);
}
