#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[500000];
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[500000];
int dsu[500000];
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[500000];
int rep[500000];
int root;
vector<int> euler;
int dep[500000];
int fuck[500000];
void dfs(int node, int prv) {
euler.push_back(node);
dep[node] = (prv == -1 ? 0 : dep[prv] + 1);
fuck[node] = min(krt[node].greenw, (prv == -1 ? (int)2e9 : fuck[prv]));
for(int x: krt[node].a) {
if(x != prv) {
dfs(x, node);
euler.push_back(node);
}
}
}
int l[500000], r[500000];
pair<int,int> st[19][500000];
int lca_idx(int x, int y) {
int m1 = min(l[x], l[y]);
int m2 = max(r[x], r[y]);
int k = 32 - __builtin_clz(m2-m1 + 1) - 1;
return min(st[k][m1], st[k][m2 - (1<<k) + 1]).second;
}
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<500000; 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;
dfs(root, -1);
for(int i=0; i<euler.size(); i++) r[euler[i]] = i;
for(int i=euler.size()-1; i>=0; i--) l[euler[i]] = i;
for(int i=0; i<euler.size(); i++) st[0][i] = {dep[euler[i]], euler[i]};
for(int i=1; i<19; i++) {
for(int j=0; j<euler.size(); j++) {
if(j+(1<<i)-1 < euler.size()) st[i][j] = min(st[i-1][j], st[i-1][j+(1<<(i-1))]);
}
}
/*
cout << "Root = " << root << "\n";
cout << "Euler tour = ";
for(int x: euler) cout << x << " ";
cout << "\n";
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";
}
cout << "test " << min(l[2], l[4]) << " " << max(r[2], r[4]) << "\n";
*/
}
int getMinimumFuelCapacity(int X, int Y) {
int q = lca_idx(X, Y);
//cout << "lca = " << q << "\n";
return (fuck[q] == 2e9 ? -1 : fuck[q]);
}
