Hitchhiking

Start Date: 13/03/18 at 10:31AM UTC

Description: Alex is hitchiking in a country with N cities, connected by M bidirectional roads. She starts at city 1, and wants to get to city N. Furthermore, while most roads are safe, some are dangerous for hitchhikers. If Alex is always able to find a ride, this problem requires you to find the minimum number of dangerous roads that must be travelled along to get to city N, and the total number of roads travelled (while minimising the number of dangerous roads).

Your input should be called Hitch.java/rb/py

INPUT

The first line contains two integers representing the number of cities (N<10001) and number of roads (M<10001).

The following M lines contain three space separated integers each. Line i is of the form Ai Bi Ti which indicates a road between cities Ai and Bi. Ti is 1 if road i is dangerous, and 0 if it is safe.

OUTPUT

If Alex cannot reach city N, the output should be -1. Otherwise, the output should be two space-separated integers consisting of the minimum number of dangerous roads and the total number of roads, that Alex must travel along to reach her destination while minimising the number of dangerous roads she goes along.

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
While Alex can travel from city 1 to city 4, this path goes along a dangerous road, which can be avoided by going from city 1 to 2, to 3 to 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
End Date: 22/03/18 at 11:59PM UTC