修路
题号：NC21126
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

最近X国的交通状况非常糟糕，所以X国打算重新修建道路。

X国共有 n 个城市，编号为 1 ~ n 。

现在开发商给出了 m 条可供修建的道路，第 i 条连接城市 ui 和 vi，长度为 li 。

X国由于不太想修建太多冗余的道路，所以只打算修筑 n-1 条道路，并且将所有城市连通起来。也就是说，这 n-1 条道路要形成一棵生成树。

在修建道路之后，X国需要规定一个中心城市 mid 。我们认为一个规划的"拥挤指数"为  ，其中  表示城市 u 到城市 v 的距离。

X国认为还有一个麻烦：有些城市会只被一条道路连接，这使得这些城市的交通不方便，会花费额外代价。

具体地，如果最终的修路方案中有 k 个城市只被一条道路连接，那么"拥挤指数"会增加 k x S ，其中 S 为给定的常数。

现在X国首领想问你，如何修建道路并规划中心城市，才能使"拥挤指数"最小呢？同时他还想问你，有几种不同的规划方案（修路+规划中心城市）能使"拥挤指数"最小呢？

输入描述:

第一行三个整数 n,m,S 。

接下来 m 行，每行三个整数 ui,vi,li ，描述一条道路。

输出描述:

一行两个整数 ，表示最小的"拥挤指数"，和达到最小"拥挤指数"的方案数。
示例1

输入

复制 
3 3 3
1 2 2
1 3 4
2 3 3

输出

复制 
11 1

说明

只有一种规划方案最优：选上 1,3 号边，并令中心城市为 2 号节点。
示例2

输入

复制 
4 6 5
1 2 3
1 3 4
1 4 5
2 3 4
2 4 5
3 4 5

输出

复制 
25 4

说明

如果选择 1,2,5 号边，可以令中心城市为 1 号节点或者 2 号节点。

如果选择 1,3,4 号边，可以令中心城市为 1 号节点或者 2 号节点。

共 4 种方案。
示例3

输入

复制 
2 1 1
1 2 1

输出

复制 
3 2

备注:

对于  的数据，有  。

对于  的数据，有  。

对于额外  的数据，有  。

对于额外  的数据，有  。

对于额外  的数据，有  。

对于额外  的数据，有  。

对于所有  的数据，有 

保证没有重边和自环。

保证将所有边都修建以后，所有城市连通。