Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque, defaultdict
import sys
input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    adj = [[] for _ in range(N+1)]
    for _ in range(M):
        p, q, c = map(int, input().split())
        adj[p].append((q, c))
        adj[q].append((p, c))

    deq = deque()
    cost = [10 ** 7] * (N+1)
    seen = [defaultdict(int) for _ in range(N+1)]
    prev = defaultdict(list)
    deq.append(1)
    cost[1] = 0
    flag = [1] * (N+1)
    while deq:
        v = deq.pop()
        flag[v] = 1
        for uc in adj[v]:
            u, c = uc
            # print(v, u, c)
            # print(deq, prev, cost)
            # print(seen[4])
            if c in prev[v] and seen[u][c] == 0:
                if cost[u] == cost[v]:
                    prev[u].append(c)
                    if flag[u]:
                        deq.append(u)
                        flag[u] = 0
                elif cost[u] > cost[v]:
                    cost[u] = cost[v]
                    deq.append(u)
                    flag[u] = 0
                    prev[u] = [c]
                seen[v][c] = 1
            else:
                if cost[u] > cost[v] + 1:
                    cost[u] = cost[v] + 1
                    deq.appendleft(u)
                    flag[u] = 0
                    prev[u] = [c]
                elif cost[u] == cost[v] + 1:
                    prev[u].append(c)

    print(cost[N]) if cost[N] < 10 ** 7 else print(-1)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    import sys
    from collections import deque
    input = sys.stdin.readline

    N, M = map(int, input().split())
    adj = [[] for _ in range(N+1)]
    c2v = {}
    v = N+1
    for _ in range(M):
        p, q, c = map(int, input().split())
        P = p*(10**7) + c
        Q = q*(10**7) + c
        if P not in c2v:
            c2v[P] = v
            adj[p].append((v, 1))
            adj.append([(p, 1)])
            v += 1
        if Q not in c2v:
            c2v[Q] = v
            adj[q].append((v, 1))
            adj.append([(q, 1)])
            v += 1
        adj[c2v[P]].append((c2v[Q], 0))
        adj[c2v[Q]].append((c2v[P], 0))

    que = deque()
    que.append(1)
    seen = [-1] * len(adj)
    seen[1] = 0
    while que:
        v = que.popleft()
        for u, cost in adj[v]:
            if seen[u] == -1:
                seen[u] = seen[v] + cost
                if cost:
                    que.append(u)
                else:
                    que.appendleft(u)
    print(seen[N] // 2)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque, defaultdict
import sys
input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    adj = [[] for _ in range(N+1)]
    for _ in range(M):
        p, q, c = map(int, input().split())
        adj[p].append((q, c))
        adj[q].append((p, c))

    deq = deque()
    cost = [10 ** 7] * (N+1)
    seen = [defaultdict(int) for _ in range(N+1)]
    prev = defaultdict(list)
    deq.append(1)
    cost[1] = 0
    flag = [1] * (N+1)
    while deq:
        v = deq.pop()
        flag[v] = 1
        for uc in adj[v]:
            u, c = uc
            # print(v, u, c)
            # print(deq, prev, cost)
            # print(seen[4])
            if c in prev[v] and seen[u][c] == 0:
                if cost[u] == cost[v]:
                    prev[u].append(c)
                    if flag[u]:
                        deq.append(u)
                        flag[u] = 0
                elif cost[u] > cost[v]:
                    cost[u] = cost[v]
                    deq.append(u)
                    prev[u] = [c]
                seen[v][c] = 1
            else:
                if cost[u] > cost[v] + 1:
                    cost[u] = cost[v] + 1
                    deq.appendleft(u)
                    prev[u] = [c]
                elif cost[u] == cost[v] + 1:
                    prev[u].append(c)

    print(cost[N]) if cost[N] < 10 ** 7 else print(-1)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    import sys
    from collections import deque
    input = sys.stdin.readline

    N, M = map(int, input().split())
    adj = [[] for _ in range(N+1)]
    c2v = {}
    v = N+1
    for _ in range(M):
        p, q, c = map(int, input().split())
        P = p*(10**7) + c
        Q = q*(10**7) + c
        if P not in c2v:
            c2v[P] = v
            adj[p].append((v, 1))
            adj.append([(p, 1)])
            v += 1
        if Q not in c2v:
            c2v[Q] = v
            adj[q].append((v, 1))
            adj.append([(q, 1)])
            v += 1
        adj[c2v[P]].append((c2v[Q], 0))
        adj[c2v[Q]].append((c2v[P], 0))

    que = deque()
    que.append(1)
    seen = [-1] * len(adj)
    seen[1] = 0
    while que:
        v = que.popleft()
        for u, cost in adj[v]:
            if seen[u] == -1:
                seen[u] = seen[v] + cost
                if cost:
                    que.append(u)
                else:
                    que.appendleft(u)
    print(seen[N] // 2)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque, defaultdict
import sys
input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    adj = [[] for _ in range(N+1)]
    for _ in range(M):
        p, q, c = map(int, input().split())
        adj[p].append((q, c))
        adj[q].append((p, c))
    
    deq = deque()
    cost = [10 ** 7] * (N+1)
    seen = [defaultdict(int) for _ in range(N+1)]
    prev = defaultdict(list)
    deq.append(1)
    cost[1] = 0
    while deq:
        v = deq.pop()
        for uc in adj[v]:
            u, c = uc
            # print(v, u, c)
            # print(deq, prev, cost)
            # print(seen[4])
            if c in prev[v] and seen[u][c] == 0:
                if cost[u] == cost[v]:
                    prev[u].append(c)
                    deq.append(u)
                elif cost[u] > cost[v]:
                    cost[u] = cost[v]
                    deq.append(u)
                    prev[u] = [c]
                seen[v][c] = 1
            else:
                if cost[u] > cost[v] + 1:
                    cost[u] = cost[v] + 1
                    deq.appendleft(u)
                    prev[u] = [c]
                elif cost[u] == cost[v] + 1:
                    prev[u].append(c)
    
    print(cost[N]) if cost[N] < 10 ** 7 else print(-1)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    import sys
    from collections import deque
    input = sys.stdin.readline

    N, M = map(int, input().split())
    adj = [[] for _ in range(N+1)]
    c2v = {}
    v = N+1
    for _ in range(M):
        p, q, c = map(int, input().split())
        P = p*(10**7) + c
        Q = q*(10**7) + c
        if P not in c2v:
            c2v[P] = v
            adj[p].append((v, 1))
            adj.append([(p, 1)])
            v += 1
        if Q not in c2v:
            c2v[Q] = v
            adj[q].append((v, 1))
            adj.append([(q, 1)])
            v += 1
        adj[c2v[P]].append((c2v[Q], 0))
        adj[c2v[Q]].append((c2v[P], 0))

    que = deque()
    que.append(1)
    seen = [-1] * len(adj)
    seen[1] = 0
    while que:
        v = que.popleft()
        for u, cost in adj[v]:
            if seen[u] == -1:
                seen[u] = seen[v] + cost
                if cost:
                    que.append(u)
                else:
                    que.appendleft(u)
    print(seen[N] // 2)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque, defaultdict
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
adj = [[] for _ in range(N+1)]
for _ in range(M):
    p, q, c = map(int, input().split())
    adj[p].append((q, c))
    adj[q].append((p, c))

deq = deque()
cost = [10 ** 7] * (N+1)
seen = [defaultdict(int) for _ in range(N+1)]
prev = defaultdict(list)
deq.append(1)
cost[1] = 0
while deq:
    v = deq.pop()
    for uc in adj[v]:
        u, c = uc
        # print(v, u, c)
        # print(deq, prev, cost)
        # print(seen[4])
        if c in prev[v] and seen[u][c] == 0:
            if cost[u] == cost[v]:
                prev[u].append(c)
                deq.append(u)
            elif cost[u] > cost[v]:
                cost[u] = cost[v]
                deq.append(u)
                prev[u] = [c]
            seen[v][c] = 1
        else:
            if cost[u] > cost[v] + 1:
                cost[u] = cost[v] + 1
                deq.appendleft(u)
                prev[u] = [c]
            elif cost[u] == cost[v] + 1:
                prev[u].append(c)

print(cost[N]) if cost[N] < 10 ** 7 else print(-1)


Fixed submission:
def main():
    import sys
    from collections import deque
    input = sys.stdin.readline

    N, M = map(int, input().split())
    adj = [[] for _ in range(N+1)]
    c2v = {}
    v = N+1
    for _ in range(M):
        p, q, c = map(int, input().split())
        P = p*(10**7) + c
        Q = q*(10**7) + c
        if P not in c2v:
            c2v[P] = v
            adj[p].append((v, 1))
            adj.append([(p, 1)])
            v += 1
        if Q not in c2v:
            c2v[Q] = v
            adj[q].append((v, 1))
            adj.append([(q, 1)])
            v += 1
        adj[c2v[P]].append((c2v[Q], 0))
        adj[c2v[Q]].append((c2v[P], 0))

    que = deque()
    que.append(1)
    seen = [-1] * len(adj)
    seen[1] = 0
    while que:
        v = que.popleft()
        for u, cost in adj[v]:
            if seen[u] == -1:
                seen[u] = seen[v] + cost
                if cost:
                    que.append(u)
                else:
                    que.appendleft(u)
    print(seen[N] // 2)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
from collections import deque, defaultdict
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
adj = [[] for _ in range(N+1)]
for _ in range(M):
    p, q, c = map(int, input().split())
    adj[p].append((q, c))
    adj[q].append((p, c))

deq = deque()
cost = [10 ** 7] * (N+1)
seen = [0] * (N+1)
prev = defaultdict(list)
deq.append(1)
cost[1] = 0
seen[1] = 1
while deq:
    v = deq.pop()
    for uc in adj[v]:
        u, c = uc
        if c in prev[v]:
            if cost[u] == cost[v]:
                cost[u] = cost[v]
                if seen[u] == 0:
                    deq.append(u)
                    seen[u] = 1
                prev[u].append(c)
            elif cost[u] > cost[v]:
                cost[u] = cost[v]
                if seen[u] == 0:
                    deq.append(u)
                    seen[u] = 1
                prev[u] = [c]
        else:
            if cost[u] > cost[v] + 1:
                cost[u] = cost[v] + 1
                if seen[u] == 0:
                    deq.appendleft(u)
                    seen[u] = 1
                prev[u].append(c)
            elif cost[u] == cost[v] + 1:
                prev[u].append(c)

print(cost[N]) if cost[N] < 10 ** 7 else print(-1)
x

Fixed submission:
def main():
    import sys
    from collections import deque
    input = sys.stdin.readline

    N, M = map(int, input().split())
    adj = [[] for _ in range(N+1)]
    c2v = {}
    v = N+1
    for _ in range(M):
        p, q, c = map(int, input().split())
        P = p*(10**7) + c
        Q = q*(10**7) + c
        if P not in c2v:
            c2v[P] = v
            adj[p].append((v, 1))
            adj.append([(p, 1)])
            v += 1
        if Q not in c2v:
            c2v[Q] = v
            adj[q].append((v, 1))
            adj.append([(q, 1)])
            v += 1
        adj[c2v[P]].append((c2v[Q], 0))
        adj[c2v[Q]].append((c2v[P], 0))

    que = deque()
    que.append(1)
    seen = [-1] * len(adj)
    seen[1] = 0
    while que:
        v = que.popleft()
        for u, cost in adj[v]:
            if seen[u] == -1:
                seen[u] = seen[v] + cost
                if cost:
                    que.append(u)
                else:
                    que.appendleft(u)
    print(seen[N] // 2)


if __name__ == '__main__':
    main()