Problem:


Score : 600 points

Problem Statement

Snuke's town has a subway system, consisting of N stations and M railway lines. The stations are numbered 1 through N. Each line is operated by a company. Each company has an identification number.

The i-th ( 1 \leq i \leq M ) line connects station p_i and q_i bidirectionally. There is no intermediate station. This line is operated by company c_i.

You can change trains at a station where multiple lines are available.

The fare system used in this subway system is a bit strange. When a passenger only uses lines that are operated by the same company, the fare is 1 yen (the currency of Japan). Whenever a passenger changes to a line that is operated by a different company from the current line, the passenger is charged an additional fare of 1 yen. In a case where a passenger who changed from some company A's line to another company's line changes to company A's line again, the additional fare is incurred again.

Snuke is now at station 1 and wants to travel to station N by subway. Find the minimum required fare.

Constraints

2 \leq N \leq 10^5

0 \leq M \leq 2×10^5

1 \leq p_i \leq N (1 \leq i \leq M)

1 \leq q_i \leq N (1 \leq i \leq M)

1 \leq c_i \leq 10^6 (1 \leq i \leq M)

p_i \neq q_i (1 \leq i \leq M)

Input

The input is given from Standard Input in the following format:

N M
p_1 q_1 c_1
:
p_M q_M c_M

Output

Print the minimum required fare. If it is impossible to get to station N by subway, print -1 instead.

Sample Input 1

3 3
1 2 1
2 3 1
3 1 2

Sample Output 1

1

Use company 1's lines: 1 → 2 → 3. The fare is 1 yen.

Sample Input 2

8 11
1 3 1
1 4 2
2 3 1
2 5 1
3 4 3
3 6 3
3 7 3
4 8 4
5 6 1
6 7 5
7 8 5

Sample Output 2

2

First, use company 1's lines: 1 → 3 → 2 → 5 → 6. Then, use company 5's lines: 6 → 7 → 8. The fare is 2 yen.

Sample Input 3

2 0

Sample Output 3

-1



Sample input:
3 3
1 2 1
2 3 1
3 1 2


Sample output:
1

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
    sys.setrecursionlimit(10 ** 7)

    from collections import deque

    n, m = map(int, readline().split())
    graph = [[] for _ in range(n + 1)]
    for _ in range(m):
        p, q, c = map(int, readline().split())
        graph[p].append([q, c, -1])
    q = deque([(1, 0, -1)])
    ans = float('inf')
    while q:
        now, v, c = q.popleft()
        for idx, (next, cc, cost) in enumerate(graph[now]):
            if cost != -1:
                continue
            graph[now][idx][2] = v
            if c != cc:
                graph[now][idx][2] += 1
                q.append((next, graph[now][idx][2], cc))
            else:
                q.appendleft((next, graph[now][idx][2], cc))
            if next == n:
                ans = min(ans, graph[now][idx][2])
    print(ans if ans != float('inf') else -1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
    sys.setrecursionlimit(10 ** 7)

    from collections import deque

    n, m = map(int, readline().split())
    graph = [[] for _ in range(n + 1)]
    cost = [[-1] * (n + 1) for _ in range(n + 1)]
    for _ in range(m):
        p, q, c = map(int, readline().split())
        graph[p].append((q, c))
    q = deque([(1, 0, -1)])
    while q:
        now, v, c = q.popleft()
        for next, cc in graph[now]:
            if cost[now][next] != -1:
                continue
            cost[now][next] = v
            if c != cc:
                cost[now][next] += 1
                q.append((next, cost[now][next], cc))
            else:
                q.appendleft((next, cost[now][next], cc))
    inf = float('inf')
    ans = inf
    for v in cost:
        if v[n] != -1:
            ans = min(ans, v[n])
    print(ans if ans != inf else -1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import deque

n, m = map(int, input().split())
G = [[] for _ in range(n)]
for _ in range(m):
  p, q, c = map(int, input().split())
  p -= 1
  q -= 1
  G[p].append((q, c))
  G[q].append((p, c))
que = deque()
que.append((0, -1, 0))
dist = [float("inf")]*n
while que:
  v, com, cnt = que.popleft()
  if cnt >= dist[v]:
    continue
  dist[v] = cnt
  for nv, ncom in G[v]:
    if ncom == com:
      que.appendleft((nv, ncom, cnt))
    else:
      que.append((nv, ncom, cnt+1))
if dist[-1] == float("inf"):
  print(-1)
else:
  print(dist[-1])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import deque

n, m = map(int, input().split())
G = [[] for _ in range(n)]
for _ in range(m):
  p, q, c = map(int, input().split())
  p -= 1
  q -= 1
  G[p].append((q, c))
  G[q].append((p, c))
que = deque()
que.append((0, -1, 0))
seen = set()
ans = float("inf")
while que:
  v, com, cnt = que.popleft()
  if (v, com) in seen:
    continue
  if v == n-1:
    if ans == cnt+1:
      print(cnt)
      exit()
    ans = cnt
    continue
  seen.add((v, com))
  for nv, ncom in G[v]:
    if ncom == com:
      que.appendleft((nv, ncom, cnt))
    else:
      que.append((nv, ncom, cnt+1))
if ans == float("inf"):
  print(-1)
else:
  print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import deque

n, m = map(int, input().split())
G = [[] for _ in range(n)]
for _ in range(m):
  p, q, c = map(int, input().split())
  p -= 1
  q -= 1
  G[p].append((q, c))
  G[q].append((p, c))
que = deque()
que.append((0, -1, 0))
seen = set()
ans = float("inf")
while que:
  v, com, cnt = que.popleft()
  if v == n-1:
    ans = min(ans, cnt)
    continue
  for nv, ncom in G[v]:
    if (nv, ncom) in seen:
      continue
    seen.add((nv, ncom))
    if ncom == com:
      que.appendleft((nv, ncom, cnt))
    else:
      que.append((nv, ncom, cnt+1))
if ans == float("inf"):
  print(-1)
else:
  print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import deque

n, m = map(int, input().split())
G = [[] for _ in range(n)]
for _ in range(m):
  p, q, c = map(int, input().split())
  p -= 1
  q -= 1
  G[p].append((q, c))
  G[q].append((p, c))
que = deque()
que.append((0, -1, 0))
seen = [False]*n
ans = float("inf")
while que:
  v, com, cnt = que.popleft()
  if seen[v]:
    continue
  if v == n-1:
    ans = min(ans, cnt)
    continue
  seen[v] = True
  for nv, ncom in G[v]:
    if ncom == com:
      que.appendleft((nv, ncom, cnt))
    else:
      que.append((nv, ncom, cnt+1))
if ans == float("inf"):
  print(-1)
else:
  print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import deque

n, m = map(int, input().split())
G = [[] for _ in range(n)]
for _ in range(m):
  p, q, c = map(int, input().split())
  p -= 1
  q -= 1
  G[p].append((q, c))
  G[q].append((p, c))
que = deque()
que.append((0, -1, 0))
seen = [False]*n
while que:
  v, com, cnt = que.popleft()
  if seen[v]:
    continue
  if v == n-1:
    print(cnt)
    exit()
  seen[v] = True
  for nv, ncom in G[v]:
    if ncom == com:
      que.appendleft((nv, ncom, cnt))
    else:
      que.append((nv, ncom, cnt+1))
print(-1)

Submission status: Wrong Answer

Solution code:
def resolve():
    def Dijkstra(s, edge, inf=float("inf")):
        import heapq
        d = defaultdict(lambda: inf)
        d[s] = 0
        used = set()
        used.add(s)
        queue = []
        for point, dist in edge[s]:
            heapq.heappush(queue, (point, dist))
        while queue:
            point, dist = heapq.heappop(queue)
            if point in used:
                continue
            d[point] = dist
            used.add(point)
            for nextp, nextdist in edge[point]:
                if not nextp in used:
                    heapq.heappush(queue, (nextp, dist + nextdist))
        return d
    from collections import defaultdict
    n, m = map(int, input().split())
    inf = float("inf")
    edge = defaultdict(list)
    for _ in range(m):
        p, q, c = map(int, input().split())
        p, q = p - 1, q - 1
        edge[(p, -1)].append([(p, c), 1])
        edge[(q, -1)].append([(q, c), 1])
        edge[(p, c)].append([(p, -1), 0])
        edge[(q, c)].append([(q, -1), 0])
        edge[(p, c)].append([(q, c), 0])
        edge[(q, c)].append([(p, c), 0])
    ans = Dijkstra((0, -1), edge, inf)[(n - 1, -1)]
    print(ans if ans < inf else -1)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop, heapify
import sys
input = sys.stdin.buffer.readline

N, M = map(int, input().split())
C = set()

edges = [[] for _ in range(N)]
for _ in range(M):
    fr, to, c = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append((to, c))
    edges[to].append((fr, c))
    C.add(c)

minDist = [10**18] * (N + 1)
minDistList = [set() for _ in range(N)]
minDistList[0] = C

que = [(1, 0, 0)]
while que:
    dist, f, now = heappop(que)

    for to, c in edges[now]:
        d = dist
        if not c in minDistList[now]:
            d += 1
        if minDist[to] > d:
            minDist[to] = d
            minDistList[to] = set()
            heappush(que, (d, f + 1, to))
        if minDist[to] == d:
            minDistList[to].add(c)

que = [(minDist[i], 0, i) for i in range(N)]
heapify(que)
while que:
    dist, f, now = heappop(que)

    for to, c in edges[now]:
        d = dist
        if not c in minDistList[now]:
            d += 1
        if minDist[to] > d:
            minDist[to] = d
            minDistList[to] = set()
            heappush(que, (d, f + 1, to))
        if minDist[to] == d:
            minDistList[to].add(c)

ans = minDist[N - 1]
print(ans if ans < 10**18 else -1)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
import sys
input = sys.stdin.buffer.readline

N, M = map(int, input().split())
C = set()

edges = [[] for _ in range(N)]
for _ in range(M):
    fr, to, c = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append((to, c))
    edges[to].append((fr, c))
    C.add(c)

minDist = [10**18] * (N + 1)
minDistList = [set() for _ in range(N)]
minDistList[0] = C

for _ in range(2):
    que = [(1, 0, 0)]
    while que:
        dist, f, now = heappop(que)

        for to, c in edges[now]:
            d = dist
            if not c in minDistList[now]:
                d += 1
            if minDist[to] > d:
                minDist[to] = d
                minDistList[to] = set()
                heappush(que, (d, f + 1, to))
            if minDist[to] == d:
                minDistList[to].add(c)

ans = minDist[N - 1]
print(ans if ans < 10**18 else -1)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
from collections import defaultdict

N, M = map(int, input().split())
INF = 10**18

edges = defaultdict(list)
for _ in range(M):
    fr, to, c = map(int, input().split())
    edges[(fr, c)].append((to, c, 0))
    edges[(to, c)].append((fr, c, 0))

    edges[(fr, c)].append((fr, -1, 0))
    edges[(to, c)].append((to, -1, 0))

    edges[(fr, -1)].append((fr, c, 1))
    edges[(to, -1)].append((to, c, 1))

minDist = defaultdict(lambda: INF)
que = [(0, 1, -1)]

while que:
    dist, now, c = heappop(que)

    for to, c, d in edges[(now, c)]:
        if minDist[(to, c)] > dist + d:
            minDist[(to, c)] = dist + d
            heappush(que, (dist + d, to, c))

ans = INF
for (v, _), d in minDist.items():
    if v == N and ans > d:
        ans = d
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop

N, M = map(int, input().split())
C = set()

edges = [[] for _ in range(N)]
for _ in range(M):
    fr, to, c = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append((to, c))
    edges[to].append((fr, c))
    C.add(c)

minDist = [10**18] * (N + 1)
minDistList = [set() for _ in range(N)]
minDistList[0] = C

que = [(1, True, 0, -1, 0)]
while que:
    dist, f, now, c, pr = heappop(que)

    if f and c in minDistList[pr]:
        dist -= 1

    for to, c in edges[now]:
        d = dist
        f = not c in minDistList[now]
        if f:
            d += 1
        if minDist[to] > d:
            minDist[to] = d
            minDistList[to] = set()
            heappush(que, (d, f, to, c, now))
        if minDist[to] == d:
            minDistList[to].add(c)

ans = minDist[N - 1]
print(ans if ans < 10**18 else -1)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop

N, M = map(int, input().split())
C = set()

edges = [[] for _ in range(N)]
for _ in range(M):
    fr, to, c = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append((to, c))
    edges[to].append((fr, c))
    C.add(c)

minDist = [10**18] * (N + 1)
minDistList = [set() for _ in range(N)]
minDistList[0] = C

que = [(1, 0, -1, 0, True)]
while que:
    dist, now, c, pr, f = heappop(que)

    if f and c in minDistList[pr]:
        dist -= 1

    for to, c in edges[now]:
        d = dist
        f = not c in minDistList[now]
        if f:
            d += 1
        if minDist[to] > d:
            minDist[to] = d
            minDistList[to] = set()
            heappush(que, (d, to, c, now, f))
        if minDist[to] == d:
            minDistList[to].add(c)

ans = minDist[N - 1]
print(ans if ans < 10**18 else -1)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop

N, M = map(int, input().split())
C = set()

edges = [[] for _ in range(N)]
for _ in range(M):
    fr, to, c = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append((to, c))
    edges[to].append((fr, c))
    C.add(c)

minDist = [10**18] * (N + 1)
minDistList = [set() for _ in range(N)]

que = [(0, 0, -1, 0)]
while que:
    dist, now, c, pr = heappop(que)

    if c in minDistList[pr]:
        dist -= 1

    if minDist[now] < dist:
        continue
    if minDist[now] == dist:
        minDistList[now].add(c)
        continue
    minDist[now] = dist
    minDistList[now] = set([c])

    for to, c in edges[now]:
        if minDist[to] > dist:
            heappush(que, (dist + 1, to, c, now))

ans = minDist[N - 1]
print(ans if ans < 10**18 else -1)

Submission status: Wrong Answer

Solution code:
from collections import deque

N, M = map(int, input().split())
C = set()

edges = [[] for _ in range(N)]
for _ in range(M):
    fr, to, c = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append((to, c))
    edges[to].append((fr, c))
    C.add(c)

minDist = [10**18] * N
minDistC = [set() for _ in range(N)]
minDistC[0] = C
que = deque([(1, 0)])
minDist[0] = 1

while que:
    dist, now = que.popleft()

    for to, c in edges[now]:
        if c in minDistC[now]:
            if minDist[to] > dist:
                minDist[to] = dist
                minDistC[to] = set()
                que.appendleft((dist, to))
            if minDist[to] == dist:
                minDistC[to].add(c)
        else:
            d = dist + 1
            if minDist[to] > d:
                minDist[to] = d
                minDistC[to] = set()
                que.append((d, to))
            if minDist[to] == d:
                minDistC[to].add(c)

ans = minDist[N - 1]
print(ans if ans < 10**18 else -1)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop, heapify

N, M = map(int, input().split())
C = set()

edges = [[] for _ in range(N)]
for _ in range(M):
    fr, to, c = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append((to, c))
    edges[to].append((fr, c))
    C.add(c)

minDist = [10**18] * (N + 1)
minDistList = [set() for _ in range(N)]
minDistList[0] = C

moveQue = [(1, 0)]
addQue = []

while moveQue:
    dist, now = heappop(moveQue)

    while addQue and addQue[0][0] <= dist:
        _, v, c = heappop(addQue)
        minDistList[v].add(c)

    for to, c in edges[now]:
        d = dist
        if not c in minDistList[now]:
            d += 1
        if minDist[to] > d:
            minDist[to] = d
            minDistList[to] = set()
            heappush(moveQue, (d, to))
        if minDist[to] == d:
            heappush(addQue, (d, to, c))

ans = minDist[N - 1]
print(ans if ans < 10**18 else -1)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop, heapify

N, M = map(int, input().split())
C = set()

edges = [[] for _ in range(N)]
for _ in range(M):
    fr, to, c = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append((to, c))
    edges[to].append((fr, c))
    C.add(c)

minDist = [10**18] * (N + 1)
minDistList = [set() for _ in range(N)]

que = [(1, 0, 0, c) for c in C] + [(1, 1, 0, -1)]
heapify(que)

while que:
    dist, f, now, c = heappop(que)

    if f == 0:
        minDistList[now].add(c)
        continue

    for to, c in edges[now]:
        d = dist
        if not c in minDistList[now]:
            d += 1
        if minDist[to] > d:
            minDist[to] = d
            minDistList[to] = set()
            heappush(que, (d, 1, to, -1))
        if minDist[to] == d:
            heappush(que, (d, 0, to, c))

ans = minDist[N - 1]
print(ans if ans < 10**18 else -1)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop

N, M = map(int, input().split())
C = set()

edges = [[] for _ in range(N)]
for _ in range(M):
    fr, to, c = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append((to, c))
    edges[to].append((fr, c))
    C.add(c)

minDist = [10**18] * (N + 1)
minDistList = [set() for _ in range(N)]
minDistList[0] = C

que = [(2, 0)]
while que:
    dist, now = heappop(que)
    dist -= 1

    for to, c in edges[now]:
        d = dist
        if not c in minDistList[now]:
            d += 1
        if minDist[to] > d:
            minDist[to] = d
            minDistList[to] = set()
            heappush(que, (d + 1, to))
        if minDist[to] == d:
            minDistList[to].add(c)

ans = minDist[N - 1]
print(ans if ans < 10**18 else -1)

Submission status: Wrong Answer

Solution code:
from collections import deque

N, M = map(int, input().split())
C = set()

edges = [[] for _ in range(N)]
for _ in range(M):
    fr, to, c = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append((to, c))
    edges[to].append((fr, c))
    C.add(c)

minDist = [10**18] * (N + 1)
minDistList = [set() for _ in range(N)]
minDistList[0] = C

que = deque([(0, 1)])
while que:
    now, dist = que.popleft()

    for to, c in edges[now]:
        d = dist
        if not c in minDistList[now]:
            d += 1
        if minDist[to] > d:
            minDist[to] = d
            minDistList[to] = set()
            que.append((to, d))
        if minDist[to] == d:
            minDistList[to].add(c)

ans = minDist[N - 1]
print(ans if ans < 10**18 else -1)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop

N, M = map(int, input().split())
C = set()

edges = [[] for _ in range(N)]
for _ in range(M):
    fr, to, c = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append((to, c))
    edges[to].append((fr, c))
    C.add(c)

minDist = [10**18] * (N + 1)
minDistList = [set() for _ in range(N)]
minDistList[0] = C

que = [(1, 0, 0)]
while que:
    dist, f, now = heappop(que)

    for to, c in edges[now]:
        d = dist
        if not c in minDistList[now]:
            d += 1
        if minDist[to] > d:
            minDist[to] = d
            minDistList[to] = set()
            heappush(que, (d, f + 1, to))
        if minDist[to] == d:
            minDistList[to].add(c)

ans = minDist[N - 1]
print(ans if ans < 10**18 else -1)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop

N, M = map(int, input().split())
C = set()

edges = [[] for _ in range(N)]
for _ in range(M):
    fr, to, c = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append((to, c))
    edges[to].append((fr, c))
    C.add(c)

minDist = [10**18] * (N + 1)
minDistList = [set() for _ in range(N)]
minDistList[0] = C

que = [(1, 0)]
while que:
    dist, now = heappop(que)

    for to, c in edges[now]:
        d = dist
        if not c in minDistList[now]:
            d += 1
        if minDist[to] > d:
            minDist[to] = d
            minDistList[to] = set()
            heappush(que, (d, to))
        if minDist[to] == d:
            minDistList[to].add(c)

ans = minDist[N - 1]
print(ans if ans < 10**18 else -1)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
from collections import defaultdict
from heapq import heappush, heappop,heappushpop,heapify
n,m = map(int, input().split())
link = defaultdict(list)

chg=10**8

for _ in range(m):
    p,q,c=map(int, input().split())
    link[p].append([p+chg*c,1])
    link[p+chg*c].append([p,1])

    link[q+chg*c].append([p+chg*c,0])
    link[p+chg*c].append([q+chg*c,0])

    link[q+chg*c].append([q,1])
    link[q].append([q+chg*c,1])

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
from collections import defaultdict
from heapq import heappush, heappop,heappushpop,heapify
n,m = map(int, input().split())
link = defaultdict(list)
for _ in range(m):
    p,q,c=map(int, input().split())
    p-=1
    q-=1
    c-=1
    link[(p,-1)].append([(p,c),1])
    link[(p,c)].append([(p,-1),1])
    link[(p,c)].append([(q,c),0])
    link[(q,c)].append([(p,c),0])
    link[(q,-1)].append([(q,c),1])
    link[(q,c)].append([(q,-1),1])

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n,m = map(int, input().split())
pqc=[list(map(int,input().split())) for i in range(m)]
from collections import defaultdict
from heapq import heappush, heappop,heappushpop,heapify
def dks(g,start):
    INF=float('inf')
    visited = defaultdict(int)
    hq = []
    heappush(hq, (0,start))
    cost = defaultdict(lambda: float("inf"))
    while hq:
        shortest, i = heappop(hq)
        if visited[i] != 0:
            continue
        visited[i] = 1
        cost[i] = shortest
        for j, t in g[i]:
            if visited[j] != 0:
                continue
            heappush(hq, (shortest + t, j))
    return cost

link = defaultdict(list)
for tmp in pqc:
    p,q,c=tmp
    p-=1
    q-=1
    c-=1
    link[(p,-1)].append([(p,c),1])
    link[(p,c)].append([(p,-1),1])
    link[(p,c)].append([(q,c),0])
    link[(q,c)].append([(p,c),0])
    link[(q,-1)].append([(q,c),1])
    link[(q,c)].append([(q,-1),1])

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque


def bfs01(s, t, links):
    q = deque([(0, s, -1)])  # cost, station, last-company
    visited = set()
    while q:
        d, v, e = q.popleft()
        if v == t:
            return d
        if v in visited:
            continue
        visited.add(v)
        for u, c in links[v]:
            if u in visited:
                continue
            if c == e:
                q.appendleft((d, u, c))
            else:
                q.append((d + 1, u, c))
    return -1


n, m = map(int, input().split())
links = [set() for _ in range(n)]
for line in sys.stdin:
    p, q, c = map(int, line.split())
    p -= 1
    q -= 1
    links[p].add((q, c))
    links[q].add((p, c))

print(bfs01(0, n - 1, links))

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

def dijkstra(edge,st):
    # edge=[[(v_to,dist_to_v),...],[],...]
    # initialize: def: d=dist(st,i), prev=[previous vertex in minimum path], q[]
    n=len(edge)
    d=[(0 if st==i else inf) for i in range(n)]
    prev=[0]*n
    q=[(j,i) for i,j in enumerate(d)]
    heapify(q)
    
    # calc
    while q:
        dist,cur=heappop(q)
        for dst,dist in edge[cur]:
            alt=d[cur]+dist
            if alt<d[dst]:
                d[dst]=alt
                prev[dst]=cur
                heappush(q,(alt,dst))
    return d,prev

n,m=LI()
g=defaultdict(set)
v=set()

D=10**7
for i in range(m):
    p,q,r=LI_()
    r+=1
    g[p*D].add(p*D+r)
    g[p*D+r].add(p*D)
    g[q*D].add(q*D+r)
    g[q*D+r].add(q*D)
    g[p*D+r].add(q*D+r)
    g[q*D+r].add(p*D+r)
    v.add(p*D)
    v.add(p*D+r)
    v.add(q*D)
    v.add(q*D+r)

def bfs01(g,x):
    rt=-1
    d={i:0 for i in v}
    d[x]=1
    q=deque()
    q.append((x,0,0))
    nx=None
    while q:
#        show(nx,(n-1)*D,d.values(),q,'end_q',d)
        cs,last_rw,dist=q.popleft()
        if cs>=(n-1)*D:
            rt=dist
            break
        for nx in g[cs]:
            next_rw=nx%D
            fee=0 if next_rw==0 or next_rw==last_rw else 1
            if d[nx]==0:
                d[nx]=d[cs]+1
                if fee==0:
                    q.appendleft((nx,last_rw,dist))
                else:
                    q.append((nx,next_rw,dist+1))

            
    return rt

ans=bfs01(g,0)

if ans==inf:
    ans=-1

print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

def dijkstra(edge,st):
    # edge=[[(v_to,dist_to_v),...],[],...]
    # initialize: def: d=dist(st,i), prev=[previous vertex in minimum path], q[]
    n=len(edge)
    d=[(0 if st==i else inf) for i in range(n)]
    prev=[0]*n
    q=[(j,i) for i,j in enumerate(d)]
    heapify(q)
    
    # calc
    while q:
        dist,cur=heappop(q)
        for dst,dist in edge[cur]:
            alt=d[cur]+dist
            if alt<d[dst]:
                d[dst]=alt
                prev[dst]=cur
                heappush(q,(alt,dst))
    return d,prev

n,m=LI()
g=defaultdict(set)
v=set()

D=10**7
for i in range(m):
    p,q,r=LI_()
    r+=1
    g[p*D].add(p*D+r)
    g[p*D+r].add(p*D)
    g[q*D].add(q*D+r)
    g[q*D+r].add(q*D)
    g[p*D+r].add(q*D+r)
    g[q*D+r].add(p*D+r)
    v.add(p*D)
    v.add(p*D+r)
    v.add(q*D)
    v.add(q*D+r)

def bfs01(g,x):
    rt=-1
    d={i:0 for i in v}
    d[x]=1
    q=deque()
    q.append((x,0,0))
    nx=None
    while q:
#        show(nx,(n-1)*D,d.values(),q,'end_q',d)
        cs,last_rw,dist=q.popleft()
        if cs>=(n-1)*D:
            show('end',dist,cs,q)
            rt=dist
            break
        for nx in g[cs]:
            next_rw=nx%D
            fee=0 if next_rw==0 or next_rw==last_rw else 1
            if d[nx]==0:
                d[nx]=d[cs]+1
                if fee==0:
                    q.appendleft((nx,last_rw,dist))
                else:
                    q.append((nx,next_rw,dist+1))

            
    return rt

ans=bfs01(g,0)

if ans==inf:
    ans=-1

print(ans)