#include "swap.h"
// author: yanybayev
#include "bits/stdc++.h"
using namespace std;
#define ff first
#define ss second
#define pp pop_back
#define ll long long
#define pb push_back
#define ls(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define wr cout << "------------------------" << endl
const int MAXN = 2e5 + 5;
vector<array<int, 3>> edges;
int n, m;
int par[MAXN];
int sz[MAXN];
int poss[MAXN];
int in[MAXN];
vector<int> g[MAXN];
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.pb({W[i], U[i], V[i]});
}
sort(all(edges));
// for (auto [c, a, b] : edges) cout << c << ' ' << a << ' ' << b << endl;
}
int find(int x) {
if (x == par[x]) return x;
return par[x] = find(par[x]);
};
bool merge(int x, int y) {
if ((x = find(x)) == (y = find(y))) return false;
if (sz[x] < sz[y]) swap(x, y);
sz[x] += sz[y];
par[y] = x;
poss[x] |= poss[y];
return true;
}
int getMinimumFuelCapacity(int X, int Y) {
for (int i = 0;i<n;++i) {
par[i] = i;
sz[i] = 1;
in[i] = 0;
poss[i] = 0;
g[i].clear();
}
for (auto [c, a, b] : edges) {
int P = 0;
if(ls(g[a]) <= 2) for (auto it : g[a]) if (find(it) == find(b)) P = 1;
if(ls(g[b]) <= 2) for (auto it : g[b]) if (find(it) == find(a)) P = 1;
in[a] += 1;
in[b] += 1;
merge(a, b);
if (max(in[a], in[b]) >= 3 or P) {
poss[find(a)] = 1;
}
g[a].pb(b);
g[b].pb(a);
if (find(X) == find(Y) and poss[find(Y)]) return c;
}
return -1;
}
