Elaxia has recently become obsessed with karate and has set up a fitness plan for himself, including push-ups, sit-ups, and so on. However, the only thing he has stuck with so far is morning jogging. Now, given a map of the area near the school, this map contains $N$ intersections and $M$ streets. Elaxia can only run from one intersection to another, and streets only intersect at the intersections. Every day, Elaxia runs from his dormitory to the school, where the dormitory is numbered $1$ and the school is numbered $N$. Elaxia's morning jogging plan is carried out in cycles (each consisting of several days). Since he does not like to take the same route, within one cycle, the jogging routes for each day must not intersect (at any intersection, excluding the dormitory and the school). Elaxia does not have great endurance; he wants the total distance run within a cycle to be as short as possible, but he also wants the number of days in the training cycle to be as long as possible. Besides practicing karate, Elaxia spends his other time studying and looking for girls, so he wants you to help him design a morning jogging plan that meets his requirements.

Input

The first line contains two numbers $N$ and $M$, representing the number of intersections and the number of streets.

The next $M$ lines each contain three numbers $a, b, c$, representing a street of length $c$ between intersection $a$ and intersection $b$ (directed).

Output

Two numbers: the first is the maximum number of days in a cycle, and the second is the shortest total distance under the condition that the number of days is maximized.

Examples

Input 1

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

Output 1

2 11

Subtasks

For all data, $1 \leq N \leq 200, 1 \leq M \leq 20\,000$.