Graphington Road Repair

In the mystical land of Graphington, a terrible storm has damaged many roads connecting its cities. The government has decided to repair a subset of these roads such that all cities become connected with the minimum repair cost.

You are given a graph with n cities and m undirected roads. Each road is characterized by three integers u, v, and w which represent a connection between cities u and v with a repair cost of w. Your task is to compute the minimal total repair cost required to connect all the cities. In addition, you must determine the number of distinct sets of roads (i.e., minimal spanning trees) that achieve this minimal cost. All computations of costs should be taken modulo \(10^9+7\).

If it is impossible to connect all the cities, output -1 -1.

inputFormat

The input is read from standard input (stdin) and has the following format:

n m
u1 v1 w1
u2 v2 w2
... 
um vm wm

Here, n and m are integers representing the number of cities and number of roads respectively. Each of the next m lines contains three space-separated integers u, v, and w describing a road.

outputFormat

Output two integers to standard output (stdout) separated by a space. The first integer is the minimal repair cost and the second is the number of distinct sets of roads that achieve this minimal cost, modulo \(10^9+7\). If it is impossible to connect all cities, output -1 -1.

5 6
1 2 3
1 3 4
4 2 5
5 1 2
2 3 7
3 5 6

14 1