问题 C: 千年老二

问题 C: 千年老二

时间限制: 1 Sec  内存限制: 128 MB
提交: 24  解决: 12
[提交][状态][讨论版][命题人:]

题目描述

雷婷与万钧是青梅竹马,无论是考试还是玩游戏,雷婷总是第一,而万钧总是第二,尽管万钧有做第一的实力,但他每次都会把第一让给雷婷,仅因为每次读榜单时雷霆万钧听起来是那么顺耳。这天,雷婷参加了 acm 选拔,万钧也跟着雷婷参加。题目是这样的:

有 n 个节点,编号为 1~n,有 m 条边,每条边都有一个距离。两点之间最多只有 1 条边。现在你需要选取 n-1 条边,使得所有点都连接起来都有通路。n-1 条边距离之和越小分数越高。

万钧立马意识到这道题是求最小生成树的,并且每个人的答案不能相同,万钧根据瞪眼法立马瞪出了答案,然而他还是等待雷婷先做完。现在雷婷已经找到了距离最短的1种方案,不过他俩太心有灵犀了,答案一模一样,万钧想获得第 2 名,请你帮万钧想一种方案,距离之和越短越好,但不能和雷婷的结果相同。一条边不同即可认为不同。如果找不到输出 -1。当然存在一种情况,如果雷婷的方案是没有方案求出最短距离,即表示该图没有最小生成树,即输出 -1。总之雷婷的方案是最优解的一种。

输入

存在多组数据,第一行一个正整数 t,表示有 t 组数据。

每组数据第一行有两个整数 n 和 m(2 ≤ n ≤ 100,1 ≤ m ≤ 1000),之后 m 行,每行三个正整数 s,e,w,表示 s 到 e 的双向路的权值为 w。

输出

输出次小生成树的值(如果存在多个最小生成树或仅有一个树,则次小生成树就是最小生成树,输出-1),如果不存在输出 -1。

样例输入

1
3 3
3 1 3
1 2 1
2 3 2

样例输出

4
[提交][状态]