Bob is hitchhiking from city to city. There are ~N~ cities numbered from ~1~ to ~N~ and ~M~ bidirectional roads. He starts at city ~1~ and wants to get to city ~N~. He has researched each road, and designated each one as either safe or dangerous for hitchhikers. Assuming that Bob will always be able to find a ride, find the minimum number of dangerous roads Bob must travel along to get to city ~N~. Bob also wants to know the minimum number of roads he must travel on while still minimizing the number of dangerous roads.

Constraints

Subtask 1 [20%]

All roads are dangerous.
~1 \le N, M \le 10^5~

Subtask 2 [20%]

Exactly one road is dangerous.
~1 \le N, M \le 10^5~

Subtask 3 [20%]

~1 \le N \le 10^3~
~1 \le M \le 10^5~

Subtask 4 [40%]

~1 \le N, M \le 10^5~

Input Specification

The first line contains two integers representing ~N~ and ~M~.

The following ~M~ lines contain three space-separated integers each. The ~i^\text{th}~ line contains ~a_i~, ~b_i~, and ~t_i~, indicating a road from city ~a_i~ to city ~b_i~. If ~t_i~ is ~0~, then this road is safe. Otherwise, ~t_i~ is ~1~ and this road is dangerous.

Output Specification

If Bob cannot reach city ~N~ at all, output ~-1~. Otherwise, output two space-separated integers: the minimum number of dangerous roads and the minimum number of roads while minimizing the number of dangerous roads.

Sample Input 1

4 5
1 2 0
1 3 1
1 4 1
2 3 0
3 4 0

Sample Output 1

0 3

Explanation for Sample 1

Although Bob can go directly from city ~1~ to city ~4~, this path goes along a dangerous road. He can completely avoid dangerous roads by going from city ~1~ to city ~2~ to city ~3~ and finally to city ~4~.

Sample Input 2

4 6
1 1 0
1 3 1
4 2 1
4 3 0
2 4 0
2 3 0

Sample Output 2

1 2

Sample Input 3

4 3
1 2 1
2 3 1
1 3 0

Sample Output 3

-1