3578. 次小生成树

单点时限: 2.0 sec

内存限制: 256 MB

求一个无向图的次小生成树,保证每条边的权值互不相同。

输入格式

第一行两个数 $n, m(1\leqslant n \leqslant 10^5, 1\leqslant m \leqslant 3 \times 10^5)$,表示顶点和边的数量。
接下来 $m$ 行,每行三个数 $u, v,w(1\leqslant u, v \leqslant n, 1\leqslant w \leqslant 10^6)$。
保证没有重边自环。

输出格式

输出次小生成树的边权和。

样例

Input
4 5
2 3 1
1 2 100
1 3 101
2 4 199
3 4 200
Output
301

21 人解决,43 人已尝试。

34 份提交通过,共有 235 份提交。

6.2 EMB 奖励。

创建: 6 年,6 月前.

修改: 6 年,6 月前.

最后提交: 1 年,5 月前.

来源: N/A

题目标签