## DMOPC '17 Contest 1 P3 - Hitchhiking Fun

View as PDF

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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.

#### 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

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 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

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