1493：次小生成树

题目描述

给定一张 $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

该图的最小生成树边权之和为 $10$，构造如下（可能有多种方案）：

• 边 $(1,2)$：权值 $1$
• 边 $(1,3)$：权值 $2$
• 边 $(2,4)$：权值 $3$
• 边 $(3,5)$：权值 $4$

严格次小生成树的边权之和为 $11$，可以通过在最小生成树中去掉一条边，并加入另一条边得到。例如去掉边 $(2,4)$（权值 $3$），加入边 $(3,4)$（权值 $3$）或去掉边 $(3,5)$（权值 $4$），加入边 $(4,5)$（权值 $6$）等方案。需要找到边权和最小的那个方案，即 $11$。

数据范围

• $1 \leq N \leq 10^5$
• $1 \leq M \leq 3 \times 10^5$
• $0 \leq z \leq 10^9$

图中无自环，边权值非负。

时空限制

• 时间限制：1000 ms
• 内存限制：65536 KB

提示：

1. 需要采用高效的算法才能在规定时间内通过所有测试数据。
2. 注意区分严格次小生成树（边权和必须大于最小生成树）和非严格次小生成树（边权和可以等于最小生成树）。