#include "swap.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
using namespace std;
//#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>
const int MOD = 1e9+7,inf = 2e9;
const int L = 2e5+1;
vi getter(L,inf);
struct DSU {
int n;
vi dad,change,sz;
DSU(){};
DSU(int nn) {
n = nn;
dad.resize(n),change.assign(n,inf),sz.assign(n,1);
iota(dad.begin(),dad.end(),0ll);
}
int find(int x,int t) {
if (change[x]==inf || change[x] > t) return x;
return find(dad[x],t);
}
void unite(int x,int y,int t) {
int a = find(x,t);
int b = find(y,t);
if (a == b) {
getter[a] = min(getter[a],t);
return;
}
if (sz[a] < sz[b]) swap(a,b);
dad[b] = a;
sz[a]+=sz[b];
change[b] = t;
if (getter[b] != inf) getter[a] = min(getter[a],t);
}
};
vi vv;
int idx(int xx) {
return upper_bound(all(vv),xx)-vv.begin();
}
map<int,int> realy;
DSU dsu;
int nn;
void init(int N, int M,
std::vector<int> U, std::vector<int> V, std::vector<int> W) {
nn = N;
for (int i=0;i<M;i++) vv.push_back(W[i]);
sort(all(vv));
vv.erase(unique(all(vv)),vv.end());
int cc = 1;
for (auto it : vv) realy[cc++] = it;
dsu = DSU(N);
vector<pair<int,pii>> edges;
for (int i=0;i<M;i++) edges.push_back({idx(W[i]),{U[i],V[i]}});
vi edg(N,0);
sort(all(edges));
for (auto it : edges) {
dsu.unite(it.ss.ff,it.ss.ss,it.ff);
edg[it.ss.ff]++;
edg[it.ss.ss]++;
if (edg[it.ss.ff] == 3 || edg[it.ss.ss] == 3) {
getter[dsu.find(it.ss.ff,it.ff)] = min(it.ff,getter[dsu.find(it.ss.ff,it.ff)]);
}
}
}
int getMinimumFuelCapacity(int X, int Y) {
int sz = vv.size();
int l = 1;
int r = sz;
while (l<=r) {
int m = (l+r) >> 1;
if (dsu.find(X,m) != dsu.find(Y,m)) {
l = m+1;
continue;
}
int p = dsu.find(X,m);
if (getter[p] > m) l = m+1;
else r = m-1;
}
if (l <= sz) return realy[l];
return -1;
}
