Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappush, heappop
from collections import defaultdict

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

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

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

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

minDist = defaultdict(lambda: INF)
minDist[(1, -1)] = 0
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 c in C:
    ans = min(ans, minDist[(N, c)])
print(ans if ans < INF else -1)


Fixed submission:
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)

for _ in range(2):
    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)

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappush, heappop
from collections import defaultdict

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

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

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

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

minDist = defaultdict(lambda: INF)
minDist[(1, -1)] = 0
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 c in C:
    ans = min(ans, minDist[(N, c)])
print(ans if ans < INF else -1)


Fixed submission:
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)

for _ in range(2):
    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)

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappush, heappop
from collections import defaultdict

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

edges = defaultdict(list)
C = set()
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))
    C.add(c)

minDist = defaultdict(lambda: INF)
minDist[(1, -1)] = 0
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 c in C:
    ans = min(ans, minDist[(N, c)])
print(ans if ans < INF else -1)


Fixed submission:
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)

for _ in range(2):
    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)

Buggy python submission (verdict: Time Limit Exceeded):
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 if ans < INF else -1)


Fixed submission:
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)

for _ in range(2):
    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)

Buggy python submission (verdict: Time Limit Exceeded):
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 if ans < INF else -1)


Fixed submission:
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)

for _ in range(2):
    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)