The Kingdom of Akabeko

The King of Akabeko has two princes. The king decided to divide the country into two when he abdicated, and let each prince rule the country one by one. The names of the new countries are Aka and Beko. There are N towns and M roads connecting the two towns in Akabeko. The King decided to allocate the town of Akabeko and some roads to the two countries by following the steps below.

(1) Select two towns and allocate them to Aka and Beko, respectively. (2) Select the town s that has already been allocated. In addition, select an unallocated town t that is connected by a single road from the town s. Then, the road between towns s and t and town t are distributed to the countries to which towns s are allocated. (3) Repeat (2) until it cannot be done.

In fact, the two princes are not very close to each other, so the king wants to make the distance between the two countries as large as possible. Here, the distance between the two countries is the shortest length of the road connecting the towns of Aka and Beko.

Given the town and road information of Akabeko, create a program to find the maximum distance between Akabe and Beko after distribution and how many distributions will result in such a distance. However, the two allocation results are distinguished when different towns or roads are allocated to Aka and Beko.

input

The input is given in the following format.

N M s1 t1 d1 s2 t2 d2 :: sM tM dM

The first line consists of two integers. N (2 ≤ N ≤ 100) represents the number of towns and M (N-1 ≤ M ≤ N (N-1) / 2) represents the number of roads. The next M line is given a way to connect the two towns. si and ti (1 ≤ si ≠ ti ≤ N) represent the numbers of the two towns where the i-th road connects. di (1 ≤ di ≤ 109) represents the length of the i-th path.

The input satisfies the following conditions.

• Both towns can be reached by using several roads.
• There are no more than two roads between any two towns.
• There are no more than 5 roads of the same length.

output

The maximum value of the distance between Aka and Beko after distribution and the number of combinations are output on one line separated by blanks. However, since the number of combinations after distribution can be very large, the remainder divided by 1,000,000,007 is output instead.

Example

Input

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

Output

7 18

inputFormat

input

The input is given in the following format.

N M s1 t1 d1 s2 t2 d2 :: sM tM dM

The first line consists of two integers. N (2 ≤ N ≤ 100) represents the number of towns and M (N-1 ≤ M ≤ N (N-1) / 2) represents the number of roads. The next M line is given a way to connect the two towns. si and ti (1 ≤ si ≠ ti ≤ N) represent the numbers of the two towns where the i-th road connects. di (1 ≤ di ≤ 109) represents the length of the i-th path.

The input satisfies the following conditions.

• Both towns can be reached by using several roads.
• There are no more than two roads between any two towns.
• There are no more than 5 roads of the same length.

outputFormat

output

The maximum value of the distance between Aka and Beko after distribution and the number of combinations are output on one line separated by blanks. However, since the number of combinations after distribution can be very large, the remainder divided by 1,000,000,007 is output instead.

Example

Input

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

Output

7 18

样例

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

7 18