题目描述

尊贵的 为你按下f键 知道了他喜欢的主播乔碧萝的身份，于是他开始了无尽的跑路！

他的跑路途径中有 $n$ 个城市 $m$ 条路，每条路连接了两个城市 $u,v$,被连接的两个城市可以在这条路上往返，每次经过某条路的时候都要支付一定的费用，为你按下f键的朋友为了帮助他走出阴影决定， 他每经过一条路就会帮他把这条路买下来,这样以后他就可以畅通无阻的在这条路上逃跑 (甚至其他人经过时还要给小f过路费!来表示对他的同情)。由于为你按下f键是尊贵的勇士，所以在他开始他的跑路 之旅前，他的朋友决定送他一件礼物，小f可以直接选择一条路并免费获得这条路的所有权。小f掐指一算就知道了完成自己的跑路之旅至少需要的花费，又掐jio一算就知道了自己一开始在选择一条路时有多少种选择方式 可以达到这个花费最小，他希望屏幕前的你能可怜一下他，帮帮他计算出这个结果。

表达能力过差，言简意赅给出一个无向图，求其最小生成树边权和减去最大边的值，和有多少种选择第一条边的方案能使生成树边权和减去最大边权值等于第一问的答案。

输入格式

第一行两个正整数 $n,m$。

之后的 $m$ 行，每行三个正整数 $u_i,v_i,w_i$（$1\le u_i,v_i\le n$，$0\le w_i\le 10^7$），描述一条连接结点 $u_i$ 和 $v_i$，边权为 $w_i$ 的边。

输出格式

两个整数表示 $sum$ $$ $num$ 分别小f所需要的花费，以及他有多少种选择方法。

样例

样例输入

4 4 
1 4 10
3 1 7
4 3 10
2 4 9

样例输出

16 2

样例解释

免去 4 3 10 这条边 此时的花费为16

• 路径为： 1 -> 3 -> 4 -> 2

免去 1 4 10 条边也是如此

• 路径为： 1 -> 4 -> 2 -> 4 -> 1 -> 3

共两种走法

数据范围与提示

多组输入输出

ps:(边可重复走)

输入数据保证图联通

$1 \leq n \leq 2e5 , 1\leq m \leq 2e5$