#include <bits/stdc++.h>
using namespace std;
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()
#define REP(i, n) for (int i = 0, _n = n; i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define FORE(it, s) for (__typeof(s.begin()) it = (s).begin(); it != (s).end(); ++it)
template <class U, class V> bool maximize(U &A, const V &B) { return (A < B) ? (A = B, true) : false; }
template <class U, class V> bool minimize(U &A, const V &B) { return (A > B) ? (A = B, true) : false; }
const int MAXN = 1e5 + 5;
int N, M, d[MAXN * 3], lab[MAXN * 3], par[22][MAXN * 3], deg[MAXN], weight[MAXN * 3], jump[MAXN * 3];
vector <int> ke[MAXN * 3];
bool is[MAXN * 3];
int find(int u) { return lab[u] == u ? u : lab[u] = find(lab[u]); }
void merge(int u, int v, int w) {
deg[u]++, deg[v]++;
bool More2 = (deg[u] > 2 || deg[v] > 2);
u = find(u), v = find(v);
if(u == v) {
if(is[u] == 0) is[u] = 1, weight[u] = w;
return;
}
N++;
lab[u] = lab[v] = N;
ke[N].push_back(u); ke[N].push_back(v);
is[N] = (More2 || is[u] || is[v]);
weight[N] = w;
}
void dfs(int u, int pre) {
if(is[u]) pre = u;
jump[u] = pre;
for (auto v : ke[u]) {
par[0][v] = u;
FOR(i, 1, 19) par[i][v] = par[i - 1][par[i - 1][v]];
d[v] = d[u] + 1;
dfs(v, pre);
}
}
int lca(int u, int v) {
if(d[u] < d[v]) swap(u, v);
FORD(i, 19, 0) if(d[par[i][u]] >= d[v]) {
u = par[i][u];
}
if(u == v) return u;
FORD(i, 19, 0) if(par[i][u] != par[i][v]) {
u = par[i][u];
v = par[i][v];
}
return par[0][u];
}
void init(int n, int m, vector <int> U, vector <int> V, vector <int> W) {
N = n, M = m;
vector <int> idx(m);
iota(lab, lab + N + M + 1, 0);
iota(ALL(idx), 0);
sort(ALL(idx), [&](const int &a, const int &b) { return W[a] < W[b]; });
for (auto i : idx) {
merge(U[i] + 1, V[i] + 1, W[i]);
}
weight[0] = -1; dfs(N, 0);
}
int getMinimumFuelCapacity(int X, int Y) {
return weight[jump[lca(X + 1, Y + 1)]];
}
