#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int nax = 2e5 + 3;
const int INF = 2e9;
const int lg = 18;
vector<tuple<int,int,int>>edges;
int n, m;
int nbe[nax/2], lvl[nax/2], tt = 1, st[nax/2], en[nax/2];
vector<pair<int,int>>g[nax/2];
int sz[nax/2], par[nax/2];
int deg[nax];
int sp[nax/2][lg], mxw[nax/2][lg];
bool bam[nax/2];
vector<int>elem[nax];
int find(int v) {
return par[v] = (v==par[v]) ? v : find(par[v]);
}
bool same(int u, int v) {
return find(u) == find(v);
}
void unite(int u, int v, int w) {
int root_u = find(u), root_v = find(v);
if(sz[root_u] < sz[root_v]) swap(root_u, root_v), swap(u, v);
if(bam[root_u] && bam[root_v] && deg[u]<2 && deg[v]<2) {
deg[u]++, deg[v]++;
par[root_v] = root_u;
sz[root_u] += sz[root_v];
bam[root_u] = true;
for(int x : elem[root_v]) {
elem[root_u].push_back(x);
}
elem[root_v].clear();
} else {
if(bam[root_u]) {
for(int x : elem[root_u]) {
nbe[x] = w;
}
}
if(bam[root_v]) {
for(int x : elem[root_v]) {
nbe[x] = w;
}
}
for(int x : elem[root_v]) {
elem[root_u].push_back(x);
}
elem[root_v].clear();
par[root_v] = root_u;
sz[root_u] += sz[root_v];
bam[root_u] = false;
}
}
void makeMST() {
for(int i=0; i<n; ++i) {
sz[i] = 1, par[i] = i;
bam[i] = 1;
elem[i].push_back(i);
}
for(auto [w, u, v] : edges) {
if(same(u, v)) {
int root = find(u);
if(bam[root]) {
for(int x : elem[root]) {
nbe[x] = w;
}
bam[root] = false;
}
} else {
unite(u, v, w);
g[u].emplace_back(v, w);
g[v].emplace_back(u, w);
}
}
}
void dfs(int v, int p = 0, int topar = 0, int lv = 0) {
lvl[v] = lv;
sp[v][0] = p;
mxw[v][0] = topar;
st[v] = tt++;
for(int j=1; j<lg; ++j) {
sp[v][j] = sp[sp[v][j-1]][j-1];
mxw[v][j] = max(mxw[v][j-1], mxw[sp[v][j-1]][j-1]);
}
for(auto [u, w] : g[v]) if(u!=p) {
dfs(u, v, w, lv+1);
}
en[v] = tt-1;
}
bool is_anc(int u, int v) {
return st[u] <= st[v] && en[u] >= en[v];
}
int get(int u, int v) {
int ret = 0;
for(int j=lg-1; j>=0; --j) {
if(!is_anc(sp[u][j], v)) {
ret = max(ret, mxw[u][j]);
u = sp[u][j];
}
}
if(!is_anc(u, v)) {
ret = max(ret, mxw[u][0]);
u = sp[u][0];
}
for(int j=lg-1; j>=0; --j) {
if(!is_anc(sp[v][j], u)) {
ret = max(ret, mxw[v][j]);
v = sp[v][j];
}
}
if(!is_anc(v, u)) {
ret = max(ret, mxw[v][0]);
v = sp[v][0];
}
return ret;
}
void init(int N, int M,
vector<int> U, vector<int> V, vector<int> W) {
n = N, m = M;
for(int i=0; i<M; ++i) {
edges.emplace_back(W[i], U[i], V[i]);
}
for(int i=0; i<N; ++i) {
nbe[i] = INF;
}
sort(edges.begin(), edges.end());
makeMST();
dfs(0);
}
int getMinimumFuelCapacity(int X, int Y) {
int ans = max({nbe[X], nbe[Y], get(X, Y)});
if(ans==INF) ans = -1;
return ans;
}
