#include<bits/stdc++.h>
#include <vector>
using namespace std;
#define fori(i, a, b) for(int i = (int) (a); i <= (int) (b); i++)
#define ford(i, a, b) for(int i = (int) (a); i >= (int) (b); i--)
#define ii pair<int, int>
#define fi first
#define se second
#define vi vector<int>
#define eb emplace_back
#define sp ' '
#define endl '\n'
//#define int long long
const int maxn = 2e5 + 5, inf = INT_MAX / 2;
int n, m;
vector<pair<int, ii> > E;
int deg[maxn];
int fre[maxn];
int rt[maxn];
int dep[maxn];
int pe[maxn];
vi cc[maxn];
int getrt(int i) {
if(rt[i] < 0) return i;
return getrt(rt[i]);
}
void join(int i, int j, int w) {
deg[i]++;
deg[j]++;
bool ok = max(deg[i], deg[j]) >= 3;
i = getrt(i); j = getrt(j);
// cout << w << sp << i << sp <<j << "cc" << endl;
if(i == j) ok = 1;
else {
if(rt[i] > rt[j]) swap(i, j);
rt[i] += rt[j];
rt[j] = i;
for(int t: cc[j]) cc[i].eb(t);
pe[j] = w;
dep[j] = dep[i] + 1;
}
if(ok){
for(int x: cc[i]) fre[x] = w;
cc[i].clear();
}
}
int get_lca(int u, int v) {
if(dep[u] < dep[v]) swap(u, v);
int mx = 0;
while(dep[u] > dep[v]) {
mx = max(mx, pe[u]);
u = rt[u];
}
while(u != v) {
mx = max(mx, max(pe[u], pe[v]));
u = rt[u];
v = rt[v];
}
return mx;
}
void init(int N, int M,
std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n = N;
m = M;
fori(i, 0, m - 1) {
int u = U[i] + 1, v = V[i] + 1, w = W[i];
E.eb(make_pair(w, ii(u, v)));
}
sort(begin(E), end(E));
fori(i, 1, n) {
fre[i] = inf;
rt[i] = -1;
pe[i] = -1;
cc[i].eb(i);
}
for(auto temp: E) {
join(temp.se.fi, temp.se.se, temp.fi);
}
}
int getMinimumFuelCapacity(int X, int Y) {
int u = X + 1, v = Y + 1;
// cout << get_lca(u, v) << endl;
// fori(i, 1, n) {
// cout << rt[i] << sp << pe[i] << sp << fre[i] << endl;
// }
int t = max(get_lca(u, v), min(fre[u], fre[v]));
if(t == inf) return -1;
return t;
}
