#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) begin(x), end(x)
#define SZ(x) (int)(x).size()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#include "swap.h"
const int n0 = 2e5 + 123;
int n, m, ans[n0], deg[n0], inf;
vector <array <int, 3>> e;
vector <int> dsu[n0];
vector <array <int, 2>> p[n0];
void init(int N, int M,
std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n = N, m = M;
for (int i = 0; i < m; i++)
e.pb({W[i], U[i], V[i]});
sort(all(e));
memset(& ans, 0x3f, sizeof(ans));
inf = ans[0];
for (int i = 0; i < n; i++)
p[i].pb({0, i}), dsu[i].pb(i);
for (auto i : e) {
int w = i[0], u = i[1], v = i[2];
int vc = p[v].back()[1], uc = p[u].back()[1];
if (vc == uc)
ans[vc] = min(ans[vc], w);
else {
if (SZ(dsu[vc]) < SZ(dsu[uc])) {
swap(vc, uc);
swap(v, u);
}
deg[v]++, deg[u]++;
ans[vc] = min(ans[vc], max(w, ans[uc]));
if (deg[v] > 2 || deg[u] > 2)
ans[vc] = min(ans[vc], w);
for (int x : dsu[uc]) {
dsu[vc].pb(x);
p[x].pb({w, vc});
}
}
}
}
int getMinimumFuelCapacity(int x, int y) {
int i = SZ(p[x]) - 1, j = SZ(p[y]) - 1, mt = inf;
while (i >= 0 && j >= 0 && p[x][i][1] == p[y][j][1]) {
mt = min(mt, max({ans[p[x][i][1]], p[x][i][0], p[y][j][0]}));
i--, j--;
}
return (mt == inf) ? -1 : mt;
}
