题目描述

农夫约翰在一所夜校学习算法课程，他刚刚学会了最小生成树。现在约翰意识到他的农场设计得不够高效，他想简化农场的布局。

约翰的农场可以看做一个图，农田代表图中顶点，田间小路代表图中的边，每条边有一定的长度。约翰注意到，农场中最多有三条小路有着相同的长度。约翰想删除一些小路使得农场成为一棵树，使得两块农田间只有一条路径。但是约翰想把农场设计成最小生成树，也就是农场道路的总长度最短。

请帮助约翰找出最小生成树的总长度，同时请计算出总共有多少种最小生成树？

输入格式

第 $\red{1 }$行：两个整数 $\red{N }$和 $\red{M (1 <= N <= 40,000}$; $\red{1 <= M <= 100,000)，}$分别表示农场图中的顶点数和边数。顶点编号为 $\red{1..N}$。

第 $\red{2..M+1 }$行：三个整数 $\red{a_i}$、$\red{b_i }$和 $\red{n_i (1 <= a_i, b_i <= N}$; $\red{1 <= n_i <= 1,000,000) }$表示从顶点 $\red{a_i }$到 $\red{b_i }$的一条边，长度为 $\red{n_i}$。没有边长 $\red{n_i }$将出现超过 $\red{3 }$次。

输出格式

第$\red{1}$行：两个整数代表最小生成树的长度和最小生成树的个数$\red{(mod}$ $\red{1,000,000,007).}$

样例

输入样例

4 5 
1 2 1 
3 4 1 
1 3 2 
1 4 2 
2 3 2

输出样例

4 3

提示

选择长度为 $\red{1 }$的两条边和长度为 $\red{2 }$的任何边产生长度为 $\red{4 }$的最小生成树。