Bob is hitchhiking from city to city. There are
cities numbered from
to
and
bidirectional roads. He starts at city
and wants to get to city
. 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
. 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.

Subtask 2 [20%]
Exactly one road is dangerous.

Subtask 3 [20%]


Subtask 4 [40%]

Input Specification
The first line contains two integers representing
and
.
The following
lines contain three space-separated integers each. The
line contains
,
, and
, indicating a road from city
to city
. If
is
, then this road is safe. Otherwise,
is
and this road is dangerous.
Output Specification
If Bob cannot reach city
at all, output
. 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
Copy
4 5
1 2 0
1 3 1
1 4 1
2 3 0
3 4 0
Sample Output 1
Copy
0 3
Explanation for Sample 1
Although Bob can go directly from city
to city
, this path goes along a dangerous road. He can completely avoid dangerous roads by going from city
to city
to city
and finally to city
.
Sample Input 2
Copy
4 6
1 1 0
1 3 1
4 2 1
4 3 0
2 4 0
2 3 0
Sample Output 2
Copy
1 2
Sample Input 3
Copy
4 3
1 2 1
2 3 1
1 3 0
Sample Output 3
Copy
-1
Comments