Overview

If we consider the graph formed by keeping only the passable roads (\(S_i=1\)), this problem becomes “find the shortest distance (in number of edges) from town \(1\) to town \(N\).” Since the cost of traversing each road is the same (\(1\)), we can find the minimum number of roads using breadth-first search (BFS).

Analysis

The key observation is that blocked roads can simply be ignored as if they don’t exist. The problem states “you may pass through the same town or the same road multiple times,” but when minimizing the number of roads used, there is no need to go back and forth unnecessarily.

For example:

• If you can travel \(1 \to 2 \to 3 \to N\), that uses 3 roads
• Making a detour like \(2 \to 1 \to 2\) only increases the count

Therefore, this is ultimately a shortest path problem on an undirected graph consisting only of passable roads.

Why a naive approach won’t work

Trying all possible routes from town \(1\) and finding the shortest one is not practical. The number of possible route choices is extremely large, and with constraints \(N, M \le 2 \times 10^5\), an exhaustive search will not finish in time.

How to solve it

In this problem, traversing any road costs “1 step,” so all edges can be considered to have weight \(1\). The standard technique for finding shortest distances in such a graph is breadth-first search (BFS).

In BFS:

• Start from the vertex at distance 0 (town 1)
• Then explore towns reachable in 1 step
• Then towns reachable in 2 steps
• Then towns reachable in 3 steps

and so on, exploring in order of increasing distance. Therefore, the distance when town \(N\) is first reached is the minimum number of roads.

Algorithm

1. Prepare an adjacency list g.
2. For each input road, add it as an undirected edge to g[U_i] and g[V_i] only when \(S_i=1\).
3. Prepare an array dist to manage the shortest number of roads to each town. Initialize with -1 to represent “unvisited,” and set dist[1] = 0.
4. Perform BFS using a queue.
   • Dequeue a town x
   • Look at each adjacent town y reachable from x via a passable road
   • If y is still unvisited, set dist[y] = dist[x] + 1 and enqueue it
5. After the search completes:
   • If dist[N] is -1, town \(N\) is unreachable, so output -1
   • Otherwise, that value is the answer

Concrete Example

For instance, suppose the passable roads are:

• \(1 \leftrightarrow 2\)
• \(2 \leftrightarrow 4\)
• \(1 \leftrightarrow 3\)
• \(3 \leftrightarrow 4\)

Then BFS gives:

• dist[1] = 0
• dist[2] = 1, dist[3] = 1
• dist[4] = 2

So the answer is \(2\). Indeed, \(1 \to 2 \to 4\) or \(1 \to 3 \to 4\) both use 2 roads.

Complexity

• Time complexity: \(O(N + M)\)
• Space complexity: \(O(N + M)\)

In BFS, each town is enqueued at most once, and each passable road is examined at most twice (once from each endpoint), so the overall running time is linear.

Implementation Notes

• The key point is to not add roads with \(S_i=0\) to the graph. This directly reduces the problem to a standard shortest path problem.

• Since roads are bidirectional, we perform both g[u].append(v) and g[v].append(u).

• Initializing dist with -1 is convenient because it allows managing both “unvisited” status and “shortest distance” in the same array.

• Multiple edges between the same pair of towns are not a problem. In BFS, already-visited towns are simply skipped, so it works correctly.

• Since the input size can be large, the implementation uses sys.stdin.buffer.read() for fast input reading.

  Source Code

import sys
from collections import deque

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return

    n, m = data[0], data[1]
    g = [[] for _ in range(n + 1)]

    idx = 2
    for _ in range(m):
        u = data[idx]
        v = data[idx + 1]
        s = data[idx + 2]
        idx += 3
        if s == 1:
            g[u].append(v)
            g[v].append(u)

    dist = [-1] * (n + 1)
    dist[1] = 0
    q = deque([1])

    while q:
        x = q.popleft()
        if x == n:
            break
        nd = dist[x] + 1
        for y in g[x]:
            if dist[y] == -1:
                dist[y] = nd
                q.append(y)

    print(dist[n])

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.