提高-⏱ 1000ms💾 256MB#P7048

题目描述

求无向图的严格次小生成树的边权和(权和严格大于最小生成树的最小者)。数据保证存在。

输入格式

第一行两个整数 n, m;接下来 m 行 u v w。

输出格式

一行一个整数。

数据范围

$$1 \le n \le 500,\ n-1 \le m \le 5000,\ 0 \le w \le 10^6$$

样例输入 #1
2 2
1 2 3
1 2 5
样例输出 #1
8
样例输入 #2
3 3
1 2 1
2 3 1
1 3 1
样例输出 #2
3