#include "swap.h"
#include <bits//stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag,
tree_order_statistics_node_update>
ordered_multiset;
#define ll long long
#define ld long double
#define iloop(m, h) for (ll i = m; i != h; i += (m < h ? 1 : -1))
#define jloop(m, h) for (auto j = m; j != h; j += (m < h ? 1 : -1))
#define kloop(m, h) for (auto k = m; k != h; k += (m < h ? 1 : -1))
#define lloop(m, h) for (auto l = m; l != h; l += (m < h ? 1 : -1))
#define iloop_(m, h, g) for (auto i = m; i < h; i += g)
#define jloop_(m, h, g) for (auto j = m; j < h; j += g)
#define kloop_(m, h, g) for (auto k = m; k < h; k += g)
#define lloop_(m, h, g) for (auto l = m; l < h; l += g)
#define getchar_unlocked _getchar_nolock // comment before submission
#define pll pair<ll, ll>
#define plll pair<ll, pll>
#define pllll pair<pll, pll>
#define vll vector<ll>
#define qll queue<ll>
#define dll deque<ll>
#define pqll priority_queue<ll>
#define gll greater<ll>
#define INF 1000000000000000
#define MOD1 1000000007
#define MOD2 998244353
#define MOD3 1000000009
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
ll n, m;
ll par[100005], lep[100005], rep[100005], noc[100005], h[100005], ct[100005];
ll find(ll x) {
return (par[x] == x ? x : find(par[x]));
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
n = N, m = M;
pair<ll, pll> edges[m];
iloop(0, m) edges[i] = {W[i], {U[i], V[i]}};
sort(edges, edges + m);
iloop(0, n) {
par[i] = lep[i] = rep[i] = i;
noc[i] = INF;
h[i] = 1;
ct[i] = INF;
}
ll tm, t1, t2;
iloop(0, m) {
if (find(edges[i].second.first) == find(edges[i].second.second)) {
tm = find(edges[i].second.first);
noc[tm] = min(noc[tm], edges[i].first);
continue;
}
t1 = find(edges[i].second.first), t2 = find(edges[i].second.second);
if (h[t1] < h[t2]) {swap(t1, t2); swap(edges[i].second.first, edges[i].second.second);}
if (h[t1] == h[t2]) h[t1]++;
if (lep[t1] == edges[i].second.first && lep[t2] == edges[i].second.second) {
lep[t1] = rep[t1];
rep[t1] = rep[t2];
}
else if (rep[t1] == edges[i].second.first && lep[t2] == edges[i].second.second) {
lep[t1] = lep[t1];
rep[t1] = rep[t2];
}
else if (lep[t1] == edges[i].second.first && rep[t2] == edges[i].second.second) {
lep[t1] = rep[t1];
rep[t1] = lep[t2];
}
else if (rep[t1] == edges[i].second.first && rep[t2] == edges[i].second.second) {
lep[t1] = lep[t1];
rep[t1] = lep[t2];
}
else noc[t1] = min(noc[t1], edges[i].first);
if (noc[t2] != INF) noc[t1] = min(noc[t1], edges[i].first);
ct[t2] = edges[i].first;
par[t2] = t1;
}
}
int getMinimumFuelCapacity(int X, int Y) {
ll lb = 0, ub = INF, mid, tx, ty;
while (lb < ub) {
mid = (lb + ub) >> 1;
tx = X, ty = Y;
while (ct[tx] <= mid) tx = par[tx];
while (ct[ty] <= mid) ty = par[ty];
if (tx == ty && noc[tx] <= mid) ub = mid;
else lb = mid + 1;
}
return (lb == INF ? -1 : lb);
}
