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

n, m = map(int, input().split())
G = defaultdict(set)
U = 10**6
seen = set()
for _ in range(m):
  p, q, c = map(int, input().split())
  G[p+U*c].add((q+U*c, 0))
  G[q+U*c].add((p+U*c, 0))
  G[p+U*c].add((p-U, 0))
  G[q+U*c].add((q-U, 0))
  G[p-U].add((p+U*c, 1))
  G[q-U].add((q+U*c, 1))
que = deque()
que.append((1-U, 0))
while que:
  v, cnt = que.popleft()
  if v in seen:
    continue
  if v == n-U:
    print(cnt)
    exit()
  seen.add(v)
  for nv, cost in G[v]:
    if cost == 0:
      que.appendleft((nv, cnt+cost))
    else:
      que.append((nv, cnt+cost))
print(-1)

Fixed submission:
import sys
input = sys.stdin.readline
from collections import defaultdict, deque

n, m = map(int, input().split())
G = defaultdict(set)
U = 10**6
seen = set()
for _ in range(m):
  p, q, c = map(int, input().split())
  G[p+U*c].add((q+U*c, 0))
  G[q+U*c].add((p+U*c, 0))
  G[p+U*c].add((p-U, 0))
  G[q+U*c].add((q-U, 0))
  G[p-U].add((p+U*c, 1))
  G[q-U].add((q+U*c, 1))
que = deque()
que.append((1-U, 0))
while que:
  v, cnt = que.popleft()
  if v in seen:
    continue
  if v == n-U:
    print(cnt)
    exit()
  seen.add(v)
  for nv, cost in G[v]:
    if cost == 0:
      que.appendleft((nv, cnt+cost))
    else:
      que.append((nv, cnt+cost))
print(-1)

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

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

Fixed submission:
import sys
input = sys.stdin.readline
from collections import defaultdict, deque

n, m = map(int, input().split())
G = defaultdict(set)
U = 10**6
seen = set()
for _ in range(m):
  p, q, c = map(int, input().split())
  G[p+U*c].add((q+U*c, 0))
  G[q+U*c].add((p+U*c, 0))
  G[p+U*c].add((p-U, 0))
  G[q+U*c].add((q-U, 0))
  G[p-U].add((p+U*c, 1))
  G[q-U].add((q+U*c, 1))
que = deque()
que.append((1-U, 0))
while que:
  v, cnt = que.popleft()
  if v in seen:
    continue
  if v == n-U:
    print(cnt)
    exit()
  seen.add(v)
  for nv, cost in G[v]:
    if cost == 0:
      que.appendleft((nv, cnt+cost))
    else:
      que.append((nv, cnt+cost))
print(-1)

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

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

Fixed submission:
import sys
input = sys.stdin.readline
from collections import defaultdict, deque

n, m = map(int, input().split())
G = defaultdict(set)
U = 10**6
seen = set()
for _ in range(m):
  p, q, c = map(int, input().split())
  G[p+U*c].add((q+U*c, 0))
  G[q+U*c].add((p+U*c, 0))
  G[p+U*c].add((p-U, 0))
  G[q+U*c].add((q-U, 0))
  G[p-U].add((p+U*c, 1))
  G[q-U].add((q+U*c, 1))
que = deque()
que.append((1-U, 0))
while que:
  v, cnt = que.popleft()
  if v in seen:
    continue
  if v == n-U:
    print(cnt)
    exit()
  seen.add(v)
  for nv, cost in G[v]:
    if cost == 0:
      que.appendleft((nv, cnt+cost))
    else:
      que.append((nv, cnt+cost))
print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
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])

Fixed submission:
import sys
input = sys.stdin.readline
from collections import defaultdict, deque

n, m = map(int, input().split())
G = defaultdict(set)
U = 10**6
seen = set()
for _ in range(m):
  p, q, c = map(int, input().split())
  G[p+U*c].add((q+U*c, 0))
  G[q+U*c].add((p+U*c, 0))
  G[p+U*c].add((p-U, 0))
  G[q+U*c].add((q-U, 0))
  G[p-U].add((p+U*c, 1))
  G[q-U].add((q+U*c, 1))
que = deque()
que.append((1-U, 0))
while que:
  v, cnt = que.popleft()
  if v in seen:
    continue
  if v == n-U:
    print(cnt)
    exit()
  seen.add(v)
  for nv, cost in G[v]:
    if cost == 0:
      que.appendleft((nv, cnt+cost))
    else:
      que.append((nv, cnt+cost))
print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
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
    if ncom == com:
      seen.add((nv, ncom))
      que.appendleft((nv, ncom, cnt))
    else:
      que.append((nv, ncom, cnt+1))
if ans == float("inf"):
  print(-1)
else:
  print(ans)

Fixed submission:
import sys
input = sys.stdin.readline
from collections import defaultdict, deque

n, m = map(int, input().split())
G = defaultdict(set)
U = 10**6
seen = set()
for _ in range(m):
  p, q, c = map(int, input().split())
  G[p+U*c].add((q+U*c, 0))
  G[q+U*c].add((p+U*c, 0))
  G[p+U*c].add((p-U, 0))
  G[q+U*c].add((q-U, 0))
  G[p-U].add((p+U*c, 1))
  G[q-U].add((q+U*c, 1))
que = deque()
que.append((1-U, 0))
while que:
  v, cnt = que.popleft()
  if v in seen:
    continue
  if v == n-U:
    print(cnt)
    exit()
  seen.add(v)
  for nv, cost in G[v]:
    if cost == 0:
      que.appendleft((nv, cnt+cost))
    else:
      que.append((nv, cnt+cost))
print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
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:
    ans = min(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)

Fixed submission:
import sys
input = sys.stdin.readline
from collections import defaultdict, deque

n, m = map(int, input().split())
G = defaultdict(set)
U = 10**6
seen = set()
for _ in range(m):
  p, q, c = map(int, input().split())
  G[p+U*c].add((q+U*c, 0))
  G[q+U*c].add((p+U*c, 0))
  G[p+U*c].add((p-U, 0))
  G[q+U*c].add((q-U, 0))
  G[p-U].add((p+U*c, 1))
  G[q-U].add((q+U*c, 1))
que = deque()
que.append((1-U, 0))
while que:
  v, cnt = que.popleft()
  if v in seen:
    continue
  if v == n-U:
    print(cnt)
    exit()
  seen.add(v)
  for nv, cost in G[v]:
    if cost == 0:
      que.appendleft((nv, cnt+cost))
    else:
      que.append((nv, cnt+cost))
print(-1)