#777. 战后重建

战后重建

说明


世界大战后,世界各国都变成了废墟,A国同样也未能避免战火,所有的道路和村庄都被炸毁。A国国王很清楚,要想加快国家建设,恢复以前的繁荣,第一件需要做的事情就是修路(要想富先修路)。

A国有 $n$ 个村庄,编号从 $1$ 到 $n$ ,A国国王计划出了 $m$ 条道路的建设,每条道路长 $w_i$ ,这些道路直接或间接的把所有的村庄连接起来。但国家需要用钱的地方还有很多,所以A国国王想使用最少的花费把所有的村庄连接起来(距离等于花费)。在这基础上A国国王还提出了一个问题,选择任意两个不同的点作为起点和终点,期望的距离是多少?

输入格式


第一行输入两个整数 $n,\ m$,分别表示村庄数目和计划建设的道路数目。

接下来 $m$ 行,每行有三个整数 $x,\ y,\ w_i$ ,表示计划在村庄 $x$ 和村庄 $y$  之间建设一条长度为 $w_i$ 的道路。保证 $w_i$ 互不相同。

数据范围: $1 \le n \le 10^5$ , $1 \le x,\ y \le n$ , $1 \le m ,\ w_i \le 10^6$ 。

输出格式

输出两个数,中间以空格隔开,第一个数表示最小的花费,第二个数保留小数点后两位,表示期望的距离。


样例

4 6
1 2 1
2 3 2
3 4 3
4 1 4
1 3 5
2 4 6
6 3.33