76 人解决，120 人已尝试。
122 份提交通过，共有 728 份提交。
4.5 EMB 奖励。
单点时限: 2.0 sec
内存限制: 256 MB
茫茫大海上有许多小岛，为了避免不可预知的危险，人们只能在两岛之间直线行船。先辈们找到了一个岛之间的最佳航海路线，所谓最佳航海路线，就是能够连接所有的岛且路线长度总和最小。但随着航海业的日益发展，这条路线变得日益拥挤，于是海运局聘请你寻找另外一个尽可能佳的路线，所经过的小岛与原路线不完全相同就可。
有多组测试数据。第一行两个整数 N，M （2<=N<=500），表示有 N 个岛，编号 1 到 n。之后 M 行，每行 3 个整数 u，v，w，表示从 u 岛到 v 岛的直线长度为 w。
输出一行两个数，原路线长度和与新路线长度和，如果无法找到新路线，输出-1。
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
4 4 4 -1