Nowadays, the kids are playing Super Mancunian, a modern reinvention of a classical game.
The main character of the game is, as you may have guessed, Mancunian. She is currently located at level . There are levels in the game and she is required to visit each of them at least once. Note that it is not necessary to visit the levels in order; she can visit the levels in any order she chooses to.
There are certain bidirectional pathways in the game connecting some pairs of levels. Each pathway connects two (not necessarily distinct) levels and each pair of levels have at most one pathway between them. Using pathways is the only way to travel between levels, but it is guaranteed that she can travel from any level to any other level using some number of pathways. To use a particular pathway, you need to pay a particular amount as cost. But it is a one-time payment; once that pathway is unlocked, you can use it as many times as you wish at no additional cost.
Like the rest of her clan, Mancunian also possesses a special power. She can reduce the cost of exactly one pathway in the game to .
Mancunian starts at level . What is the minimum cost she needs to pay to visit all the levels? Also, how many pathways can she choose to reduce to so that she can visit all the levels at the minimum cost?
Input Format
The first line of input contains two space-separated integers and , the number of levels in the game and the number of pathways respectively.
Each of the next lines contains three space-separated integers , and indicating that there is a bidirectional pathway between the levels and having cost .
Constraints
Subtask
- For 45% of the maximum points, and
Output Format
Print two space-separated integers, the first of which is the minimum cost incurred and the second is the number of possible pathways she can use her superpower on to achieve the minimum possible total cost. See the sample explanation for more details.
Sample Input 0
4 6
1 2 1
1 3 3
1 4 7
2 3 2
2 4 3
3 4 3
Sample Output 0
3 3
Explanation 0
The following illustrates the layout of the levels in this sample case:
The minimum total cost is , which can be shown to be the minimum possible. In addition, there are three pathways whose cost can be reduced to to achieve this minimum cost:
- Mancunian uses her superpower on the pathway between and . The path she follows could be .
- Mancunian uses her superpower on the pathway between and . The path she follows could be .
- Mancunian uses her superpower on the pathway between and . The path she follows could be .