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