#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;i++)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(),v.rend()
#define pb push_back
#define sz(a) (int)a.size()
const int N = 4e5 + 10, K = 25;
vector<int> adj[N], g[N];
int val[N], degree[N], depth[N], jump[N][K], id, n;
bool vis[N], good;
struct DSU {
vector<int> par;
DSU() {
par.assign(N, 0);
forn(i, N) par[i] = i;
}
int get(int a) {
return par[a] = (par[a] == a ? a : get(par[a]));
}
void uni(int a, int b) {
a = get(a);
b = get(b);
par[a] = b;
}
};
vector<int> component;
void get_component(int u) {
vis[u] = true;
component.pb(u);
for(int v: g[u]) {
if(!vis[v]) get_component(v);
}
}
void dfs(int u, int par) {
jump[u][0] = par;
for(int v: adj[u]) {
if(v == par) continue;
depth[v] = depth[u] + 1;
dfs(v, u);
}
}
int LCA(int u, int v) {
if(depth[u] < depth[v]) swap(u, v);
for(int j = K - 1; j >= 0; --j) {
if(depth[jump[u][j]] >= depth[v]) {
u = jump[u][j];
}
}
//cout << u << ' ' << v << ' ' << depth[u] << ' ' << depth[v] << endl;
if(u == v) return u;
for(int j = K - 1; j >= 0; --j) {
if(jump[u][j] != jump[v][j]) {
u = jump[u][j], v = jump[v][j];
}
}
//cout << u << ' ' << jump[u][0] << endl;
return jump[u][0];
}
void init(int _n, int m, vector<int> U, vector<int> V, vector<int> W) {
n = _n;
id = n;
vector<array<int, 3>> edges;
DSU d;
DSU connect;
for(int i = 0; i < m; ++i) {
edges.pb({W[i], U[i], V[i]});
}
sort(all(edges));
for(auto x: edges) {
int u = x[1], v = x[2], w = x[0];
g[u].pb(v);
g[v].pb(u);
if(d.get(u) == d.get(v)) continue;
if(d.get(u) == u) swap(u, v);
if(d.get(u) != u && d.get(v) != v) {
adj[id].pb(d.get(u));
adj[id].pb(d.get(v));
d.uni(u, id);
d.uni(v, id);
val[id] = w;
++id;
} else if(d.get(u) != u) {
component.clear();
get_component(v);
for(auto x: component) {
adj[id].pb(x);
d.uni(x, id);
}
val[id] = w;
++id;
adj[id].pb(d.get(u));
adj[id].pb(d.get(v));
d.uni(u, id);
d.uni(v, id);
val[id] = w;
++id;
} else {
++degree[u];
++degree[v];
if(connect.get(u) == connect.get(v) || degree[u] > 2 || degree[v] > 2) {
component.clear();
get_component(u);
good = true;
for(auto x: component) {
d.uni(x, id);
adj[id].pb(x);
}
val[id] = w;
++id;
} else{
connect.uni(u, v);
}
}
}
dfs(id - 1, id - 1);
for(int k = 1; k < K; ++k) {
for(int i = 0; i < N; ++i) {
jump[i][k] = id - 1;
}
}
for(int k = 1; k < K; ++k) {
for(int i = 0; i < N; ++i) {
jump[i][k] = jump[jump[i][k - 1]][k - 1];
}
}
}
int getMinimumFuelCapacity(int u, int v) {
if(!good) return -1;
return val[LCA(u, v)];
}
/*
void solve() {
int NN, m; cin >> NN >> m;
vector<int> a(m), b(m), c(m);
forn(i, m) cin >> a[i];
forn(i, m) cin >> b[i];
forn(i, m) cin >> c[i];
init(NN, m, a, b, c);
cout << getMinimumFuelCapacity(1, 2) << "\n";
cout << getMinimumFuelCapacity(2, 4) << "\n";
cout << getMinimumFuelCapacity(0, 1) << "\n";
}
int32_t main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t = 1;
//cin >> t;
while(t--) {
solve();
}
}
*/
