次小生成树

题目内容

题目描述

给定一个n个顶点(n <= 500),m条边(m <= 100000)的无向图,将其所有的生成树按树上的边的权值和从小到大排序,求排在第二位的生成树的权值大小。两棵生成树只要有任意一条非公共边,则认为这两棵生成树不同。

输入描述

输入的第一行为两个整数n,m。

接下来m行,每行3个整数a,b,c,代表顶点a和顶点b之间有一条无向边,该边的权值为c。权值为小于1000的正整数,输入保证没有重边或自环。

输出描述

输出一行,为题目所求的生成树的权值大小。如果不存在满足条件的生成树,则输出-1.

样例输入

4 4 1 2 1 2 3 1 3 4 1 4 1 1

样例输出

3

提示

提交评测
请登录后再操作

题目描述

次小生成树
1175
0
Level3
22
12
55%
证书查询 x
请输入证书编号:

请输入正确的证书编号

学员姓名:孙兴民

课程:Scratch Level 1

发证日期:2019.08.15

证书查询

该证书不存在