#include "bits/stdc++.h"
using namespace std;
//#define int long long
const int MAXN = 2e5 + 10;
const int MOD = 1e9 + 7;
#define ll __int128
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
ll read() { // read int128
int x; cin >> x; return (ll)x;
}
long long bm(long long b, long long p) {
if(p==0) return 1 % MOD;
long long r = bm(b, p >> 1);
if(p&1) return (((r*r) % MOD) * b) % MOD;
return (r*r) % MOD;
}
long long inv(long long b) {
return bm(b, MOD-2);
}
long long f[MAXN];
long long nCr(int n, int r) {
long long ans = f[n]; ans *= inv(f[r]); ans %= MOD;
ans *= inv(f[n-r]); ans %= MOD; return ans;
}
void precomp() {
for(int i=0; i<MAXN; i++) f[i] = (i == 0 ? 1 % MOD : (f[i-1] * i) % MOD);
}
int fastlog(int x) {
if(x == 0) return -1;
return 32 - __builtin_clz(x) - 1;
}
void gay(int i) {
cout << "Case #" << i << ": ";
}
#include "swap.h"
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W);
int getMinimumFuelCapacity(int X, int Y);
int n, m;
vector<pair<int,int> > adj[101010];
struct edge {
int f, t, w;
};
class cmp {
public:
bool operator() (edge x, edge y) {
return x.w>y.w;
}
};
vector<edge> mst;
edge e[101010];
int dsu[101010];
int set_of(int u) {
if(dsu[u]==u) return u;
return dsu[u]= set_of(dsu[u]);
}
void union_(int u, int v) {
dsu[set_of(u)] = set_of(v);
}
struct node {
vector<int> a; // children
int par; // parenty
int blackw, greenw; // minimum weight limit s.t. subtree is pairwise reachable
int madeg = 0; // max degree
} krt[202020];
int rep[202020];
int root;
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n = N, m = M;
for(int i=0; i<m; i++) {
adj[U[i]].push_back({V[i], W[i]});
adj[V[i]].push_back({U[i], W[i]});
e[i] = {U[i], V[i], W[i]};
}
for(int i=0; i<n; i++) dsu[i] = i;
priority_queue<edge, vector<edge>, cmp> pq;
for(int i=0; i<m; i++) pq.push(e[i]);
int newnode = n;
for(int i=0; i<n; i++) rep[i] = i;
for(int i=0; i<202020; i++) krt[i].blackw = 0, krt[i].greenw = 2e9, krt[i].par = -1;
int deg[n];
for(int i=0; i<n; i++) deg[i] = 0;
// Conditions: either cycle or max degree ≥ 3 (i.e. NOT chain)
while(pq.size()) {
deg[pq.top().f]++;
deg[pq.top().t]++;
if(set_of(pq.top().f) != set_of(pq.top().t)) {
int st1 = rep[set_of(pq.top().f)];
int st2 = rep[set_of(pq.top().t)];
krt[newnode].a.push_back(st1);
krt[newnode].a.push_back(st2);
krt[st1].par = krt[st2].par = newnode;
union_(pq.top().f, pq.top().t);
rep[set_of(pq.top().f)] = newnode;
krt[newnode].madeg = max({krt[st1].madeg, krt[st2].madeg, deg[pq.top().f], deg[pq.top().t]});
krt[newnode].blackw = pq.top().w;
if(krt[newnode].madeg >= 3 || krt[st1].greenw != 2e9 || krt[st2].greenw != 2e9) {
krt[newnode].greenw = pq.top().w;
}
else {
krt[newnode].greenw = 2e9;
}
newnode++;
}
else { // update all the way to the root, update max degree array and green weights
int rt = rep[set_of(pq.top().f)];
//cout << "root = " << rt << "\n";
if(krt[rt].greenw == 2e9) { // O(component size) is ok
int now = pq.top().f;
unordered_map<int, int> vis;
while(now != rt) {
now = krt[now].par;
vis[now] = 1;
}
now = pq.top().t;
while(now != rt) {
now = krt[now].par;
if(vis[now]) {
// common ancestor
krt[now].greenw = pq.top().w;
}
}
}
}
pq.pop();
}
root = newnode - 1;
/*
for(int i=newnode - 1; i >= 0; i--) {
cout << "node " << i << ": black = " << krt[i].blackw << ", green = " << krt[i].greenw << ", max degree = " << krt[i].madeg << "\n";
for(int x: krt[i].a) cout << i << " " << x << "\n";
}
*/
}
int getMinimumFuelCapacity(int X, int Y) {
unordered_map<int, int> omg;
while(X != root) {
X = krt[X].par;
omg[X] = 1;
}
while(Y != root) {
Y = krt[Y].par;
if(omg[Y] && krt[Y].greenw != 2e9) {
return krt[Y].greenw;
}
}
return -1;
}
