Free and Paid Roads

Difficulty: 1800 4000 ms 128 MB

bfs graphs

Every road costs either 0 or 1. Print the cheapest cost from node 1 to node N, or −1.

Input: the first line has N and M; each of the next M lines has u v w with w ∈ {0, 1}.

Output: the minimum cost, or −1.

Constraints:

• 2 ≤ N ≤ 10⁴
• 1 ≤ M ≤ 2×10⁴

Sample Tests

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

1

2 1
1 2 0

0

Read the Editorial