A facility has n rooms (numbered 0 to n-1) joined by two-way corridors. Each corridor is either already open (you may walk through it for free) or locked (you must spend one keycard charge to open and pass through it, in either direction).
Starting in room 0, you want to reach room n-1. Find the minimum total number of keycard charges spent (equivalently, the fewest locked corridors you must pass through). If room n-1 cannot be reached at all, report that it is impossible.
Input format
Line 1: two integers n and m (rooms and corridors).
Each of the next m lines: three integers u v w, a two-way corridor between rooms u and v, where w is 0 (open) or (locked).
Output format
A single integer: the minimum number of keycard charges to get from room 0 to room n-1, or -1 if unreachable.
Constraints
- 1 <= n <= 100000
- 0 <= m <= 200000
- 0 <= u, v <= n-1
- w is 0 or 1