One morning, you wake up to find that it snowed hard overnight, and that school buses have now been cancelled. To celebrate, you decide to go tobogganing at the giant hill in your neighbourhood. At the top of the hill, you see that there are several possible paths down the hill, and that each path may split, merge, or intersect with others at "scenic points". More specifically, there are ~N~ scenic points numbered from ~1~ to ~N~, and ~M~ paths from point ~a_i~ to point ~b_i~ that have a length of ~d_i~.
You want to take the longest path down (from point ~1~ to point ~N~), but would also like to stop at the greatest number of scenic points, while prioritizing the longest path. What would be the greatest distance that you can slide, as well as the number of scenic points that you would stop at on that particular route?
The first line of input will contain ~N~ and ~M~, space-separated integers. The next ~M~ lines will each contain 3 space-separated integers ~a_i~, ~b_i~, and ~d_i~, representing a path from point ~a_i~ to point ~b_i~ with a length of ~d_i~.
Note: paths are not bidirectional. It would not be possible to slide up a hill.
For all subtasks, ~1 \le a_i < N~, ~1 < b_i \le N~, and ~a_i \ne b_i~.
Subtask 1 [10%]
- ~1 < N \le 100~
- ~1 \le M \le 1\,000~
- ~d_i = 1~
Subtask 2 [90%]
- ~1 < N \le 1\,000~
- ~1 \le M \le 100\,000~
- ~1 \le d_i \le 1\,000\,000~
Output the total distance of the longest route possible and the number of scenic points on that route, separated by a space. Output ~-1~ if it is not possible to reach the bottom of the hill, or if any paths form a cycle.
Sample Input 1
6 7 1 2 1 1 3 2 2 4 2 2 5 2 3 6 2 4 6 2 5 6 1
Sample Output 1
Path 1 ~\rightarrow~ 2 ~\rightarrow~ 4 ~\rightarrow~ 6 has a length of 5, and visits 4 scenic points.
Path 1 ~\rightarrow~ 2 ~\rightarrow~ 5 ~\rightarrow~ 6 has a length of 4, and visits 4 scenic points.
Path 1 ~\rightarrow~ 3 ~\rightarrow~ 6 has a length of 4, and visits 3 scenic points.
Therefore, the path that should be chosen is the first one, as it is the longest.
Sample Input 2
5 5 1 2 1 2 3 2 2 4 3 3 1 2 4 5 1
Sample Output 2
There is a cycle (1 ~\rightarrow~ 2 ~\rightarrow~ 3 ~\rightarrow~ 1). Since you can't go down a hill and end up at the top, this is an impossible scenario.