提高-⏱ 1000ms💾 256MB#P7048🏷️ 图论最小生成树

题目描述

求无向图的严格次小生成树的边权和(权和严格大于最小生成树的最小者)。若不存在(包括"数据保证存在"不满足的情形),输出 -1。

输入格式

第一行两个整数 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
5
样例输入 #2
3 3
1 2 1
2 3 1
1 3 1
样例输出 #2
-1