题目描述

给定一张带权无向连通图，求这张图的严格次小生成树的边权和。

一棵生成树的边权和严格大于最小生成树的边权和，并且在所有满足这一条件的生成树中边权和最小，则称它为严格次小生成树。

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示点数和边数。

接下来 $m$ 行，每行包含三个整数 $u,v,w$，表示点 $u$ 与点 $v$ 之间有一条边权为 $w$ 的无向边。

输出格式

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

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

11

数据范围与提示

• $1 \le n \le 10^5$
• $1 \le m \le 3 imes 10^5$
• $1 \le u,v \le n$
• $0 \le w \le 10^9$
• 保证图连通

来源

一本通 3.1 练习 6，LOJ #10133