#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
//implement persistent DSU
ll N1,M1;
const ll Nm = 1e5+5;
vector<int> W;
vector<pii> f[Nm]; //DSU forward
vector<pii> sz[Nm]; //DSU size
vector<pii> cd[Nm]; //DSU condition
ll deg[Nm]; //degree
//0 -> not OP, 1 -> OP
ll getf(ll x, ll wc) { //WRITE
if (f[x].back().second==x) {
return x;
} else {
ll y = getf(f[x].back().second,wc);
// if (f[x].back().first==wc) {
// f[x].pop_back();
// }
// f[x].push_back({wc,y});
return y;
}
}
ll getfR(ll x, ll wc) { //READ
auto A0 = lower_bound(f[x].begin(),f[x].end(),(pii){wc+1,-1});
A0--;
ll y = (*A0).second;
if (x==y) {
return x;
}
return getfR(y,wc);
}
ll getCD(ll x, ll wc) {
x = getfR(x,wc);
auto A0 = lower_bound(cd[x].begin(),cd[x].end(),(pii){wc+1,-1});
A0--;
return (*A0).second;
}
ll fz(ll a, ll b, ll wc) {
//cout << "fuse a,b,wc="<<a<<","<<b<<","<<wc<<"\n";
deg[a]++;
deg[b]++;
bool SET = (deg[a]>=3)||(deg[b]>=3);
a = getf(a,wc);
b = getf(b,wc);
//cout << "new a, new b="<<a<<","<<b<<"\n";
if (a==b) {
if (cd[a].back().first==wc) {
cd[a].pop_back();
}
cd[a].push_back({wc,1});
return a;
}
if (sz[a].back().second>sz[b].back().second) {
swap(a,b);
}
if (f[a].back().first==wc){
f[a].pop_back();
}
f[a].push_back({wc,b});
if (sz[b].back().first==wc) {
sz[b].pop_back();
}
sz[b].push_back({wc,sz[a].back().second+sz[b].back().second});
if (cd[b].back().first==wc) {
cd[b].pop_back();
}
cd[b].push_back({wc,(ll)((cd[b].back().second==1)||(cd[a].back().second==1))});
if (SET) {
if (cd[b].back().first==wc) {
cd[b].pop_back();
}
cd[b].push_back({wc,1});
}
return b;
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W1) {
N1 = N; M1=M;
vector<array<ll,3>> vedg;
for (ll i=0;i<Nm;i++) {
f[i].push_back({0,i});
sz[i].push_back({0,1});
cd[i].push_back({0,0});
deg[i]=0;
}
for (ll i=0;i<M;i++) {
vedg.push_back({W1[i],U[i],V[i]});
}
W = W1;
sort(W.begin(),W.end());
sort(vedg.begin(),vedg.end());
for (auto A0: vedg) {
fz(A0[1],A0[2],A0[0]);
}
for (ll i=0;i<Nm;i++) {
for (ll x=0;x<(f[i].size()-1);x++) {
assert(f[i][x].first<f[i][x+1].first);
}
for (ll x=0;x<(sz[i].size()-1);x++) {
assert(sz[i][x].first<sz[i][x+1].first);
}
for (ll x=0;x<(cd[i].size()-1);x++) {
assert(cd[i][x].first<cd[i][x+1].first);
}
}
}
int getMinimumFuelCapacity(int a, int b) {
if (N1<=3 || M1==0) {
return -1;
}
ll xmin = 0; ll xmax = W.size();
while (xmin!=xmax) {
ll xt = (xmin+xmax)/2;
ll wt = W[xt];
ll a1 = getfR(a,wt);
ll b1 = getfR(b,wt);
if (a1==b1 && getCD(a1,wt)==1) {
xmax = xt;
} else {
xmin = xt+1;
}
}
if (xmin==W.size()) {
return -1;
}
return W[xmin];
}
