#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
#ifndef DEBUG
#define cerr if (0) cerr
#endif
#define INF 1000000005
#define LINF 1000000000000000005ll
#define MAXL 20
#define MAXN 200005
int n, m;
vector<iii> edges;
vii oadj[MAXN], adj[MAXN];
int l[MAXN];
ii p[MAXL][MAXN];
int omn[MAXL][MAXN];
namespace dsu {
int p[MAXN], rnk[MAXN];
int findp(int u) {
if (p[u] == u) return u;
return p[u] = findp(p[u]);
}
bool join(int a, int b) {
int pa = findp(a), pb = findp(b);
if (pa == pb) return 0;
if (rnk[pa] < rnk[pb]) swap(pa, pb);
if (rnk[pa] == rnk[pb]) rnk[pa]++;
p[pb] = pa;
return 1;
}
}
void dfs(int u) {
REP (k, 1, MAXL) {
if (p[k - 1][u].FI == -1) {
p[k][u] = MP(-1, -1);
} else {
p[k][u].FI = p[k - 1][p[k - 1][u].FI].FI;
p[k][u].SE = max(p[k - 1][u].SE, p[k - 1][p[k - 1][u].FI].SE);
}
}
for (auto [v, w] : adj[u]) {
if (v == p[0][u].FI) continue;
l[v] = l[u] + 1;
p[0][v] = MP(u, w);
dfs(v);
}
}
int dp[MAXN], rdp[MAXN], cost[MAXN];
void dfsdp(int u, int p) {
dp[u] = cost[u] = INF;
for (auto [v, w] : adj[u]) {
if (v == p) continue;
dfsdp(v, u);
mnto(dp[u], max(dp[v], w));
}
if (oadj[u].size() >= 3) {
mnto(dp[u], oadj[u][2].SE);
mnto(cost[u], oadj[u][2].SE);
}
REP (i, 0, min((int) oadj[u].size(), 4)) {
bool die = 0;
for (auto [v, w] : adj[u]) {
if (v == oadj[u][i].FI) {
die = 1;
break;
}
}
if (!die) {
mnto(dp[u], oadj[u][i].SE);
mnto(cost[u], oadj[u][i].SE);
}
}
cerr << u << ": " << dp[u] << "\n";
}
void reroot(int u, int p) {
vi pre(adj[u].size());
vi suf(adj[u].size());
REP (i, 0, adj[u].size()) {
auto [v, w] = adj[u][i];
pre[i] = suf[i] = max(dp[v], w);
}
REP (i, 1, adj[u].size()) {
mnto(pre[i], pre[i - 1]);
}
RREP (i, adj[u].size() - 2, 0) {
mnto(suf[i], suf[i + 1]);
}
dp[u] = min(suf[0], cost[u]);
rdp[u] = dp[u];
cerr << u << ": " << rdp[u] << "\n";
REP (i, 0, adj[u].size()) {
auto [v, w] = adj[u][i];
if (v == p) continue;
dp[u] = min(cost[u], min(i == 0 ? INF : pre[i - 1],
i + 1 == adj[u].size() ? INF : suf[i + 1]));
cerr << " " << u << " " << v << ": " << dp[u] << "\n";
reroot(v, u);
}
}
void init(int n, int m, vi u, vi v, vi w) {
#ifndef DEBUG
ios::sync_with_stdio(0), cin.tie(0);
#endif
REP (i, 0, n) {
dsu::p[i] = i;
dsu::rnk[i] = 0;
}
::n = n; ::m = m;
REP (i, 0, m) {
oadj[u[i]].pb(MP(v[i], w[i]));
oadj[v[i]].pb(MP(u[i], w[i]));
edges.pb(MT(w[i], u[i], v[i]));
}
REP (i, 0, n) {
sort(ALL(oadj[i]), [&] (ii l, ii r) {
if (l.SE == r.SE) return l.FI < r.FI;
return l.SE < r.SE;
});
}
sort(ALL(edges));
for (auto [w, u, v] : edges) {
if (dsu::join(u, v)) {
adj[u].pb(MP(v, w));
adj[v].pb(MP(u, w));
}
}
p[0][0] = MP(-1, -1);
dfs(0);
dfsdp(0, -1);
reroot(0, -1);
}
// consider other path from x to y
// second mst
int getMinimumFuelCapacity(int x, int y) {
cerr << x << " " << y << "\n";
if (l[x] < l[y]) swap(x, y);
int ox = x, oy = y;
int cmx = -INF;
RREP (k, MAXL - 1, 0) {
if (p[k][x].FI == -1) continue;
if (l[p[k][x].FI] > l[y]) {
mxto(cmx, p[k][x].SE);
x = p[k][x].FI;
cerr << "jump " << k << " " << x << "\n";
}
}
cerr << " " << x << " " << y << "\n";
if (p[0][x].FI == y) {
mxto(cmx, p[0][x].SE);
x = p[0][x].FI;
} else {
if (l[x] != l[y]) {
mxto(cmx, p[0][x].SE);
x = p[0][x].FI;
}
assert(l[x] == l[y]);
RREP (k, MAXL - 1, 0) {
if (p[k][x].FI != p[k][y].FI) {
mxto(cmx, p[k][x].SE);
x = p[k][x].FI;
mxto(cmx, p[k][y].SE);
y = p[k][y].FI;
}
}
mxto(cmx, p[0][x].SE);
mxto(cmx, p[0][y].SE);
}
mxto(cmx, rdp[ox]);
if (cmx >= INF) {
return -1;
}
return cmx;
}
/*
10 9
0 1 9
0 2 8
0 3 4
0 4 5
0 5 3
0 6 1
0 7 8
0 8 4
0 9 6
10
0 8
0 5
3 9
2 4
1 7
6 8
1 2
5 6
3 4
5 6
*/
