2614 - 电力修建

假设你是电力公司的工程师,目前需要为一个城镇的n个村庄铺设电力系统,现在测量出m条,村落x与村落y之间的直线距离z,每个村落之间的编号为1至n,现在要求你用最小的成本完成电力系统的铺设,使得整个城镇的居民都能用上电。目前我国电力电力铺设均采用高压输电,假设电力铺设造价为w万元/km。

输入

第一行输入两个正整数n,m表示城镇共有几个村庄,和测量出几对村庄间的直线距离。(1<=n<=100)

接下来的m行每行输入3个正整数,表示x村落到y村落的直线距离z。

最后一行输入1个正整数表示电力铺设的每公里造价。

输出

输出一行两个正整数表示铺设电力系统的最优路程是多少,总共造价是多少。

样例

输入

7 10
1 2 5
1 3 7
1 7 2
2 4 9
3 5 8
4 5 4
5 7 4
5 6 5
6 7 6
7 2 3
8

输出

25 200
时间限制 1 秒
内存限制 512 MB
讨论 统计
上一题 下一题