题目描述

给定一张 $N$ 个点 $M$ 条边的无向图，求无向图的严格次小生成树。

设最小生成树的边权之和为 $sum$，严格次小生成树就是指边权之和大于 $sum$ 的生成树中最小的一个。

输入格式

第一行包含两个整数 $N$ 和 $M$，表示无向图的点数与边数；

接下来 $M$ 行，每行三个数 $x, y, z$，表示点 $x$ 和点 $y$ 之间有一条边，边的权值为 $z$。

输出格式

输出一行，仅一个数，表示严格次小生成树的边权和。

数据保证必定存在严格次小生成树。

样例

输入样例 1

5 6 
1 2 1 
1 3 2 
2 4 3 
3 5 4 
3 4 3 
4 5 6

输出样例 1

11

样例解释

图如下：

1--(1)--2
|        \
(2)       (3)
|          \
3--(3)--4--(6)--5
   (4)

最小生成树（Prim 或 Kruskal）： 选取边权最小的边：$(1,2,1), (1,3,2), (3,4,3), (3,5,4)$，总权值 $1+2+3+4=10$。

严格次小生成树： 可以用一条非树边替换一条树边，且替换后仍为树，并且总权值严格大于 $10$ 且最小。

• 非树边 $(2,4,3)$：替换树边 $(3,4,3)$，权值不变（$10$），不是严格大于。
• 非树边 $(4,5,6)$：替换树边 $(3,5,4)$，新权值 $10-4+6=12$。
• 非树边 $(3,4,3)$ 已在树中。
• 还有其他替换方式：比如替换 $(1,3,2)$ 为 $(2,4,3)$，则需断开 $(1,3)$ 并加入 $(2,4)$，但这样可能不连通，需要检查环：加入 $(2,4)$ 会与 $(1,2),(1,3),(3,4)$ 形成环，应删除环上最大边 $(3,4,3)$，新权值 $10-3+3=10$，不变。 更优的替换：用 $(2,4,3)$ 替换 $(1,2,1)$？加入 $(2,4)$ 会与 $(1,2),(1,3),(3,4)$ 形成环，删除环上最大边 $(3,4,3)$，新权值 $10-3+3=10$，不变。 用 $(4,5,6)$ 替换 $(3,4,3)$？加入 $(4,5)$ 会与 $(3,4),(3,5)$ 形成环，删除环上最大边 $(3,5,4)$，新权值 $10-4+6=12$。 实际上严格次小生成树权值是 $11$，可能是用 $(3,4,3)$ 替换 $(3,5,4)$？但 $(3,4,3)$ 已在树中，不能替换。 正确做法：枚举所有非树边 $(u,v,w)$，找到树上 $u$ 到 $v$ 路径上的最大边权 $max1$ 和严格次大边权 $max2$，若 $w > max1$，则替换后权值 $sum - max1 + w$；若 $w = max1$，则替换后权值 $sum - max2 + w$。取所有替换方案的最小值。 计算可得严格次小生成树权值为 $11$。

数据范围

• $1 \le N \le 10^5$
• $1 \le M \le 3 \times 10^5$
• 边权值非负且不超过 $10^9$
• 保证存在严格次小生成树

时间限制：1000 ms
内存限制：524288 KB

提示

算法步骤：

1. 用 Kruskal 算法求出最小生成树，记录总权值 $sum$ 和树边集合。
2. 建立最小生成树的树结构（无根树转有根树），预处理倍增数组：$fa[u][k]$ 表示 $u$ 的 $2^k$ 级祖先，$max1[u][k]$ 表示 $u$ 到 $fa[u][k]$ 路径上的最大边权，$max2[u][k]$ 表示严格次大边权。
3. 枚举每条不在最小生成树中的边 $(u,v,w)$，在树上查询 $u$ 到 $v$ 路径上的最大边权 $m1$ 和严格次大边权 $m2$。
   • 如果 $w > m1$，则可以用这条边替换权值为 $m1$ 的树边，新总权值 $sum - m1 + w$。
   • 如果 $w = m1$，则必须用 $w$ 替换严格次大边权 $m2$ 才能得到严格更大的生成树（因为 $m2 < m1$），新总权值 $sum - m2 + w$。
4. 取所有新总权值的最小值即为答案。

注意：

• 严格次小生成树要求权值严格大于最小生成树，因此当 $w = m1$ 时，不能替换 $m1$（否则权值不变），必须替换 $m2$。
• 查询路径最大和次大边权时，需要合并多个跳跃区间的信息，注意合并时要区分最大和次大。
• 时间复杂度：Kruskal $O(M \log M)$，预处理 $O(N \log N)$，枚举非树边 $O(M \log N)$，可以通过。