#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
using vi = vector<int>;
using ii = pair<int, int>;
using vii = vector<ii>;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vb = vector<bool>;
using pll = pair<ll, ll>;
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define pb push_back
#define eb emplace_back
#define ef emplace_front
#define fst first
#define snd second
const int INF = 1e9 + 200;
struct DSU {
vector<vii> p;
vector<vii> isGood;
vi deg;
DSU(int n = 0) : p(n, vii(1, make_pair(0, -1))), isGood(n, vii(1, make_pair(0, 0))), deg(n, 0) {}
int find(int t, int x) {
auto it = prev(lower_bound(all(p[x]), make_pair(t + 1, -INF)));
if (it->snd < 0) return x;
return find(t, it->snd);
}
int findLast(int x) {
if (p[x].back().snd < 0) return x;
return findLast(p[x].back().snd);
}
void unite(int t, int x, int y) {
bool flag = ++deg[x] == 3 || ++deg[y] == 3;
x = findLast(x), y = findLast(y);
if (x == y) {
isGood[x].eb(t, 1);
return;
}
if (p[x].back().snd > p[y].back().snd) swap(x, y);
p[x].eb(t, p[x].back().snd + p[y].back().snd);
p[y].eb(t, x);
isGood[x].eb(t, isGood[x].back().snd || isGood[y].back().snd || flag);
}
bool same(int t, int x, int y) {
return find(t, x) == find(t, y);
}
bool good(int t, int x) {
x = find(t, x);
auto it = prev(lower_bound(all(isGood[x]), make_pair(t + 1, -INF)));
return it->snd;
}
};
vector<tuple<int, int, int>> edges;
int n;
DSU dsu;
void init(int N, int M, vi U, vi V, vi W) {
forn(i, M) edges.eb(W[i], U[i], V[i]);
n = N, sort(all(edges));
dsu = DSU(N);
int t = 0;
for (auto [w, u, v] : edges) {
dsu.unite(++t, u, v);
}
}
int getMinimumFuelCapacity(int X, int Y) {
int lo = 0, hi = sz(edges) + 1;
while (hi - lo > 1) {
int mid = (lo + hi) / 2;
if (dsu.same(mid, X, Y) && dsu.good(mid, X)) {
hi = mid;
} else {
lo = mid;
}
}
if (lo == sz(edges)) return -1;
return get<0>(edges[lo]);
}
