往届 ACM 队训练题 (参考)

1086. 强大的lwc

单点时限: 2.0 sec

内存限制: 256 MB

lwc 喜欢睡懒觉,每天起的很晚,但是又不想迟到,于是他就想走最近的路。但是大家都知道,由于修建实验楼,很多路被封掉了。为了不迟到,强大的 lwc 决定自己修一些道路,使他有道路可以从宿舍到任何的教学楼,但是修建每条道路需要花费一定精力,现在要求满足上述要求时最少的精力。设宿舍楼为 0,教学楼为 1,2,3…n, 现在输入 n,m, 分别代表 n 栋楼,m 代表可以修建的方法数。

输入格式

第一行为 t,表示 case 数

2 个数 n,m 分别代表 n 栋楼,m 种方法数 (0<n<=100,0<m<10000)

接下来 m 行:

a b c 分别代表 a 楼 b 楼,造 a 到 b 的道路所需要花费的精力为 c

(a->b 和 b->a 等价,a->b 的路可能会有多条)

输出格式

每组数据输出一行。

输出总的最少精力,如果不存在修建方案输出-1;

样例

Input
2
2 1
1 2 2
2 2
0 1 2
1 2 3
Output
-1
5
不限期开放

题目列表