2165. 寻找航海路线

单点时限: 2.0 sec

内存限制: 256 MB

茫茫大海上有许多小岛,为了避免不可预知的危险,人们只能在两岛之间直线行船。先辈们找到了一个岛之间的最佳航海路线,所谓最佳航海路线,就是能够连接所有的岛且路线长度总和最小。但随着航海业的日益发展,这条路线变得日益拥挤,于是海运局聘请你寻找另外一个尽可能佳的路线,所经过的小岛与原路线不完全相同就可。

输入格式

有多组测试数据。第一行两个整数 N,M (2<=N<=500),表示有 N 个岛,编号 1 到 n。之后 M 行,每行 3 个整数 u,v,w,表示从 u 岛到 v 岛的直线长度为 w。

输出格式

输出一行两个数,原路线长度和与新路线长度和,如果无法找到新路线,输出-1。

样例

Input
4 6
1 2 2
2 3 2
3 4 2
4 1 2
1 3 1
2 4 1
3 2
1 2 2
2 3 2
Output
4 4
4 -1

59 人解决,96 人已尝试。

102 份提交通过,共有 630 份提交。

4.8 EMB 奖励。

创建: 12 年,4 月前.

修改: 3 年,2 月前.

最后提交: 3 周,2 天前.

来源: DLL

题目标签