题意就是要求一个图的严格次小生成树。以前被题面吓到了没敢做，写了一下发现并不难。
既然要考虑次小我们就先考虑最小。可以感性理解到一定有一种次小生成树，可以由最小生成树删一条边再加一条边得到。我们枚举加上去的这一条边，加上去以后原\(mst\)会成为一个基环树，想让它次小就在这个环里找一条最长的边（不包含新加进去的）删掉就好。放在树上来讲，就是找到\(u\)到\(v\)路径上的最大值。这样我们就有了非严格次小生成树。
严格要怎么处理？我们需要排除新加上的边和\(u\)到\(v\)路径最长边相等的情况。仔细思考会发现可以再倍增维护一个次大长度，如果最大长度严格小于新加上边的长度就选用最大，否则就用次大。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100000 + 5;
const int M = 300000 + 5;
const int INF = 0x7fffffff;
const LL INFF = 0x7fffffffffffffff;
struct Graph {
int cnt, head[N];
struct Edge {int nxt, to, w;}e[N << 1];
void clear () {
cnt = -1;
memset (head, -1, sizeof (head));
}
void add_len (int u, int v, int w) {
e[++cnt] = (Edge) {head[u], v, w}; head[u] = cnt;
e[++cnt] = (Edge) {head[v], u, w}; head[v] = cnt;
}
int deep[N], pre[N][20], w1st[N][20], w2nd[N][20];
void dfs (int u, int fa) {
deep[u] = deep[fa] + 1;
for (int i = head[u]; ~i; i = e[i].nxt) {
int v = e[i].to;
if (v != fa) {
dfs (v, u);
pre[v][0] = u;
w2nd[v][0] = -INF;
w1st[v][0] = e[i].w;
}
}
}
void build (int u) {
for (int i = 1; (1 << i) <= deep[u]; ++i) {
pre[u][i] = pre[pre[u][i - 1]][i - 1];
w1st[u][i] = max (w1st[u][i - 1], w1st[pre[u][i - 1]][i - 1]);
w2nd[u][i] = max (w2nd[u][i - 1], w2nd[pre[u][i - 1]][i - 1]);
if (w1st[u][i - 1] < w1st[pre[u][i - 1]][i - 1]) {
w2nd[u][i] = max (w2nd[u][i], w1st[u][i - 1]);
}
if (w1st[u][i - 1] > w1st[pre[u][i - 1]][i - 1]) {
w2nd[u][i] = max (w2nd[u][i], w1st[pre[u][i - 1]][i - 1]);
}
}
for (int i = head[u]; ~i; i = e[i].nxt) {
if (e[i].to != pre[u][0]) build (e[i].to);
}
}
int lca (int u, int v) {
if (deep[u] < deep[v]) swap (u, v);
for (int i = 19; i >= 0; --i) {
if (deep[u] - deep[v] >= (1 << i)) {
u = pre[u][i];
}
}
if (u == v) return u;
for (int i = 19; i >= 0; --i) {
if (pre[u][i] != pre[v][i]) {
u = pre[u][i];
v = pre[v][i];
}
}
return pre[u][0];
}
int query (int u, int v, int w) {
//求u到v之间严格小于w的最大的值
int ans = -INF;
for (int i = 19; i >= 0; --i) {
if (deep[v] - deep[u] >= (1 << i)) {
if (w1st[v][i] < w) {
ans = max (ans, w1st[v][i]);
} else {
ans = max (ans, w2nd[v][i]);
}
v = pre[v][i];
}
}
return ans;
}
}G;
struct Len {
int u, v, w;
bool operator < (Len rhs) const {
return w < rhs.w;
}
Len () {}
Len (int u, int v, int w) : u(u), v(v), w(w) {}
}arr[M];
int n, m, Set[N], in_mst[M];
int find (int x) {
return x == Set[x] ? x : (Set[x] = find (Set[x]));
}
int main () {
G.clear ();
cin >> n >> m;
for (int i = 0; i < m; ++i) {
static int u, v, w;
cin >> u >> v >> w;
arr[i] = Len (u, v, w);
}
sort (arr, arr + m);
for (int i = 0; i <= n; ++i) Set[i] = i;
LL mstw = 0;
for (int i = 0; i < m; ++i) {
int u = arr[i].u;
int v = arr[i].v;
int w = arr[i].w;
if (find (u) != find (v)) {
mstw += w;
in_mst[i] = true;
G.add_len (u, v, w);
Set[find (u)] = find (v);
}
}
G.w1st[1][0] = -INF;
G.dfs (1, 0);
G.build (1);
LL ans = INFF;
for (int i = 0; i < m; ++i) {
if (!in_mst[i]) {
int u = arr[i].u;
int v = arr[i].v;
int w = arr[i].w;
int _lca = G.lca (u, v);
int maxu = G.query (_lca, u, w);
int maxv = G.query (_lca, v, w);
ans = min (ans, mstw + w - max (maxu, maxv));
}
}
cout << ans << endl;
}