|
|
|
|
描述 Description |
|
|
|
xiaomengxian的哥哥是一个游戏迷，他喜欢研究各种游戏。这天，xiaomengxian到他家玩，他便拿出了自己最近正在研究的一个游戏给xiaomengxian看。这个游戏是这样的：一个国家有N个城市，有些城市之间可以建设铁路，并且不同城市之间建设铁路的费用各不相同。问如何用最小的费用，使整个国家的各个城市之间能够互相到达。另外，铁路是双向的。xiaomengxian心想，这不是太简单了吗？这就是经典的MST问题。他的哥哥说，这个当然不算什么。关键是它还要求费用第二小的方案，这真是让人伤脑筋。xiaomengxian想了很久，也没有想出来，你能帮助他吗？
费用第二小的方案的定义为：与费用最小的方案不完全相同，且费用值除费用最小的方案外最小。
|
|
|
|
|
|
|
|
输入格式 Input Format |
|
| |
第一行两个数N（2<=N<=500），M，分别表示国家的城市数和可以修建铁路的城市有多少对。
接下来M行，每行三个正整数Ai，Bi，Ci，表示城市Ai和Bi之间可以修建铁路，费用为Ci。
|
|
|
|
|
|
|
|
输出格式 Output Format |
|
| |
第一行：”Cost: “+一个整数，表示最小费用。（若不存在，输出-1）
第二行：”Cost: “+一个整数，表示第二小费用。（若不存在，输出-1）
|
|
|
|
|
|
|
|
时间限制 Time Limitation |
|
|
|
各个测试点1s |
|
|
|
|
|
|
|
注释 Hint |
|
|
|
Sample input #2
3 2
1 2 2
2 3 2
Sample output #2
Cost: 4
Cost: -1
|
|
|
|
|
|
|
|
|
Flag |
|
题号 |
P1376 |
|
其它 |
通过 |
0人 |
提交 |
0次 |
通过率 |
0% |
难度 |
3 |
|
|
|
|
|
|
