题目描述

Farmer John has been taking an evening algorithms course at his local university, and he has just learned about minimum spanning trees. However, Farmer John now realizes that the design of his farm is not as efficient as it could be, and he wants to simplify the layout of his farm.

The farm is currently arranged like a graph, with vertices representing fields and edges representing pathways between these fields, each having an associated length. Farmer John notes that for each distinct length, at most three pathways on his farm share this length. FJ would like to remove some of the pathways on his farm so that it becomes a tree -- that is, so that there is one unique route between any pair of fields. Moreover, Farmer John would like this to be a minimum spanning tree -- a tree having the smallest possible sum of edge lengths.

Help Farmer John compute not only the sum of edge lengths in a minimum spanning tree derived from his farm graph, but also the number of different possible minimum spanning trees he can create.

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

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

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

输入格式

* Line 1: Two integers N and M (1 <= N <= 40,000; 1 <= M <= 100,000), representing the number of vertices and edges in the farm graph, respectively. Vertices are numbered as 1..N.

* Lines 2..M+1: Three integers a_i, b_i and n_i (1 <= a_i, b_i <= N; 1 <= n_i <= 1,000,000) representing an edge from vertex a_i to b_i with length n_i. No edge length n_i will occur more than three times.

输出格式

* Line 1: Two integers representing the length of the minimal spanning tree and the number of minimal spanning trees (mod

1,000,000,007).

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

4 3 

提示

Picking both edges with length 1 and any edge with length 2 yields a minimum spanning tree of length 4.