Buggy python submission (verdict: Runtime Error):
from collections import defaultdict,deque
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
N,M=map(int,input().split())
if M==0:
  print(-1)
  exit()
G=defaultdict(set)
for i in range(M):
  a,b,c=map(int,input().split())
  G[a+(c<<30)].add(b+(c<<30))
  G[b+(c<<30)].add(a+(c<<30))
  G[a].add(a+(c<<30))
  G[b].add(b+(c<<30))
  G[a+(c<<30)].add(a)
  G[b+(c<<30)].add(b)
def BFS(x):
  d={}
  for k in G.keys():
    d[k]=float("inf")
  stack=deque([(x,0)])
  while stack:
    s,m=stack.popleft()
    if s==N:
      return m
    if d[s]>m:
      d[s]=m
      if s>=(1<<30):
        for i in G[s]:
          if d[i]>10**30:
            stack.appendleft((i,m))
      else: 
        for i in G[s]:
          if d[i]>10**30:
            stack.append((i,m+1))
  return -1

print(BFS(1))



      
    

Fixed submission:
from collections import defaultdict,deque
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
N,M=map(int,input().split())
if M==0:
  print(-1)
  exit()
G=defaultdict(set)
for i in range(M):
  a,b,c=map(int,input().split())
  G[a+(c<<30)].add(b+(c<<30))
  G[b+(c<<30)].add(a+(c<<30))
  G[a].add(a+(c<<30))
  G[b].add(b+(c<<30))
  G[a+(c<<30)].add(a)
  G[b+(c<<30)].add(b)
def BFS(x):
  d={}
  for k in G.keys():
    d[k]=float("inf")
  stack=deque([(x,0)])
  if x not in d:
    return -1
  while stack:
    s,m=stack.popleft()
    if s==N:
      return m
    if d[s]>m:
      d[s]=m
      if s>=(1<<30):
        for i in G[s]:
          if d[i]>10**30:
            stack.appendleft((i,m))
      else: 
        for i in G[s]:
          if d[i]>10**30:
            stack.append((i,m+1))
  return -1

print(BFS(1))

Buggy python submission (verdict: Runtime Error):
from collections import defaultdict,deque
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
if M==0:
  print(-1)
  exit()
G=defaultdict(set)
for i in range(M):
  a,b,c=map(int,input().split())
  G[a+(c<<30)].add(b+(c<<30))
  G[b+(c<<30)].add(a+(c<<30))
  G[a].add(a+(c<<30))
  G[b].add(b+(c<<30))
  G[a+(c<<30)].add(a)
  G[b+(c<<30)].add(b)
def BFS(x):
  d={}
  for k in G.keys():
    d[k]=float("inf")
  stack=deque([(x,0)])
  while stack:
    s,m=stack.popleft()
    if s==N:
      return m
    if d[s]>m:
      d[s]=m
      if s>=(1<<30):
        for i in G[s]:
          if d[i]>10**30:
            stack.appendleft((i,m))
      else: 
        for i in G[s]:
          if d[i]>10**30:
            stack.append((i,m+1))
  return -1

print(BFS(1))



      
    

Fixed submission:
from collections import defaultdict,deque
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
N,M=map(int,input().split())
if M==0:
  print(-1)
  exit()
G=defaultdict(set)
for i in range(M):
  a,b,c=map(int,input().split())
  G[a+(c<<30)].add(b+(c<<30))
  G[b+(c<<30)].add(a+(c<<30))
  G[a].add(a+(c<<30))
  G[b].add(b+(c<<30))
  G[a+(c<<30)].add(a)
  G[b+(c<<30)].add(b)
def BFS(x):
  d={}
  for k in G.keys():
    d[k]=float("inf")
  stack=deque([(x,0)])
  if x not in d:
    return -1
  while stack:
    s,m=stack.popleft()
    if s==N:
      return m
    if d[s]>m:
      d[s]=m
      if s>=(1<<30):
        for i in G[s]:
          if d[i]>10**30:
            stack.appendleft((i,m))
      else: 
        for i in G[s]:
          if d[i]>10**30:
            stack.append((i,m+1))
  return -1

print(BFS(1))

Buggy python submission (verdict: Runtime Error):
from collections import defaultdict,deque
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
if M==0:
  print(-1)
  exit()
G=defaultdict(set)
for i in range(M):
  a,b,c=map(int,input().split())
  G[a+c<<30].add(b+c<<30)
  G[b+c<<30].add(a+c<<30)
  G[a].add(a+c<<30)
  G[b].add(b+c<<30)
  G[a+c<<30].add(a)
  G[b+c<<30].add(b)
def BFS(x):
  d={}
  for k in G.keys():
    d[k]=float("inf")
  stack=deque([(x,0)])
  while stack:
    s,m=stack.popleft()
    if s==N:
      return m
    if d[s]>m:
      d[s]=m
      if s>=(1<<30):
        for i in G[s]:
          if d[i]>10**7:
            stack.appendleft((i,m))
      else: 
        for i in G[s]:
          if d[i]>10**7:
            stack.append((i,m+1))
  return -1

print(BFS(1))



      
    

Fixed submission:
from collections import defaultdict,deque
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
N,M=map(int,input().split())
if M==0:
  print(-1)
  exit()
G=defaultdict(set)
for i in range(M):
  a,b,c=map(int,input().split())
  G[a+(c<<30)].add(b+(c<<30))
  G[b+(c<<30)].add(a+(c<<30))
  G[a].add(a+(c<<30))
  G[b].add(b+(c<<30))
  G[a+(c<<30)].add(a)
  G[b+(c<<30)].add(b)
def BFS(x):
  d={}
  for k in G.keys():
    d[k]=float("inf")
  stack=deque([(x,0)])
  if x not in d:
    return -1
  while stack:
    s,m=stack.popleft()
    if s==N:
      return m
    if d[s]>m:
      d[s]=m
      if s>=(1<<30):
        for i in G[s]:
          if d[i]>10**30:
            stack.appendleft((i,m))
      else: 
        for i in G[s]:
          if d[i]>10**30:
            stack.append((i,m+1))
  return -1

print(BFS(1))

Buggy python submission (verdict: Runtime Error):
from collections import defaultdict,deque
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
G=defaultdict(set)
for i in range(M):
  a,b,c=map(int,input().split())
  G[(a-1,c-1)].add((b-1,c-1))
  G[(b-1,c-1)].add((a-1,c-1))
  G[(a-1,-1)].add((a-1,c-1))
  G[(b-1,-1)].add((b-1,c-1))
  G[(a-1,c-1)].add((a-1,-1))
  G[(b-1,c-1)].add((b-1,-1))
def BFS(x):
  d={}
  for k in G.keys():
    d[k]=float("inf")
  d[x]=0
  stack=deque([(x,-1,0)])
  while stack:
    a,c,m=stack.popleft()
    if a==N-1 and c==-1:
      return m
    if d[(a,c)]>m:
      d[(a,c)]=m
      if c>=0:
        for i in G[(a,c)]:
          if d[i]>10**30:
            stack.appendleft((i[0],i[1],m))
      else: 
        for i in G[(a,c)]:
          if d[i]>10**30:
            stack.append((i[0],i[1],m+1))
  return -1

print(BFS(0))



      
    

Fixed submission:
from collections import defaultdict,deque
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
N,M=map(int,input().split())
if M==0:
  print(-1)
  exit()
G=defaultdict(set)
for i in range(M):
  a,b,c=map(int,input().split())
  G[a+(c<<30)].add(b+(c<<30))
  G[b+(c<<30)].add(a+(c<<30))
  G[a].add(a+(c<<30))
  G[b].add(b+(c<<30))
  G[a+(c<<30)].add(a)
  G[b+(c<<30)].add(b)
def BFS(x):
  d={}
  for k in G.keys():
    d[k]=float("inf")
  stack=deque([(x,0)])
  if x not in d:
    return -1
  while stack:
    s,m=stack.popleft()
    if s==N:
      return m
    if d[s]>m:
      d[s]=m
      if s>=(1<<30):
        for i in G[s]:
          if d[i]>10**30:
            stack.appendleft((i,m))
      else: 
        for i in G[s]:
          if d[i]>10**30:
            stack.append((i,m+1))
  return -1

print(BFS(1))

Buggy python submission (verdict: Runtime Error):
from collections import defaultdict,deque
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
G=defaultdict(set)
for i in range(M):
  a,b,c=map(int,input().split())
  G[(a-1,c-1)].add((b-1,c-1))
  G[(b-1,c-1)].add((a-1,c-1))
  G[(a-1,-1)].add((a-1,c-1))
  G[(b-1,-1)].add((b-1,c-1))
  G[(a-1,c-1)].add((a-1,-1))
  G[(b-1,c-1)].add((b-1,-1))
def BFS(x):
  d={}
  for k in G.keys():
    d[k]=float("inf")
  d[x]=0
  stack=deque([(x,-1,0)])
  while stack:
    a,c,m=stack.popleft()
    if a==N-1 and c==-1:
      return m
    d[(a,c)]=min(d[(a,c)],m)
    if c>=0:
      for i in G[(a,c)]:
        if d[i]>10**30:
          stack.appendleft((i[0],i[1],m))
    else: 
      for i in G[(a,c)]:
        if d[i]>10**30:
          stack.append((i[0],i[1],m+1))
  return -1

print(BFS(0))



      
    

Fixed submission:
from collections import defaultdict,deque
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
N,M=map(int,input().split())
if M==0:
  print(-1)
  exit()
G=defaultdict(set)
for i in range(M):
  a,b,c=map(int,input().split())
  G[a+(c<<30)].add(b+(c<<30))
  G[b+(c<<30)].add(a+(c<<30))
  G[a].add(a+(c<<30))
  G[b].add(b+(c<<30))
  G[a+(c<<30)].add(a)
  G[b+(c<<30)].add(b)
def BFS(x):
  d={}
  for k in G.keys():
    d[k]=float("inf")
  stack=deque([(x,0)])
  if x not in d:
    return -1
  while stack:
    s,m=stack.popleft()
    if s==N:
      return m
    if d[s]>m:
      d[s]=m
      if s>=(1<<30):
        for i in G[s]:
          if d[i]>10**30:
            stack.appendleft((i,m))
      else: 
        for i in G[s]:
          if d[i]>10**30:
            stack.append((i,m+1))
  return -1

print(BFS(1))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict,deque
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
G=defaultdict(set)
Comps=[[] for i in range(N)]
for i in range(M):
  a,b,c=map(int,input().split())
  G[(a-1,c-1)].add((b-1,c-1,0))
  G[(b-1,c-1)].add((a-1,c-1,0))
  Comps[a-1].append(c-1)
  Comps[b-1].append(c-1)
for i in range(N):
  for c in Comps[i]:
    G[(i,-1)].add((i,c,1))
    G[(i,c)].add((i,-1,0))
def BFS(x):
  visited=defaultdict(bool)
  stack=deque([(x,-1,0)])
  ans=0
  while stack:
    a,c,m=stack.popleft()
    if visited[(a,c)]:
      continue
    if a==N-1 and c==-1:
      return m
    for i in G[(a,c)]:
      if not visited[(i[0],i[1])]:
        if i[2]==0:
          stack.appendleft((i[0],i[1],m))
        else:
          stack.append((i[0],i[1],m+1))
    visited[(a,c)]=True
  return -1

print(BFS(0))



      
    

Fixed submission:
from collections import defaultdict,deque
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
N,M=map(int,input().split())
if M==0:
  print(-1)
  exit()
G=defaultdict(set)
for i in range(M):
  a,b,c=map(int,input().split())
  G[a+(c<<30)].add(b+(c<<30))
  G[b+(c<<30)].add(a+(c<<30))
  G[a].add(a+(c<<30))
  G[b].add(b+(c<<30))
  G[a+(c<<30)].add(a)
  G[b+(c<<30)].add(b)
def BFS(x):
  d={}
  for k in G.keys():
    d[k]=float("inf")
  stack=deque([(x,0)])
  if x not in d:
    return -1
  while stack:
    s,m=stack.popleft()
    if s==N:
      return m
    if d[s]>m:
      d[s]=m
      if s>=(1<<30):
        for i in G[s]:
          if d[i]>10**30:
            stack.appendleft((i,m))
      else: 
        for i in G[s]:
          if d[i]>10**30:
            stack.append((i,m+1))
  return -1

print(BFS(1))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict,deque
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
G0=defaultdict(set)
G1=defaultdict(set)
Comps=[[] for i in range(N)]
for i in range(M):
  a,b,c=map(int,input().split())
  G0[(a-1,c-1)].add((b-1,c-1))
  G0[(b-1,c-1)].add((a-1,c-1))
  Comps[a-1].append(c-1)
  Comps[b-1].append(c-1)
for i in range(N):
  for c in Comps[i]:
    G1[(i,-1)].add((i,c))
    G0[(i,c)].add((i,-1))
def BFS(x):
  visited=defaultdict(bool)
  stack=deque([(x,-1,0)])
  while stack:
    a,c,m=stack.popleft()
    if visited[(a,c)]:
      continue
    if a==N-1 and c==-1:
      return m
    for i in G0[(a,c)]:
      if not visited[(a,c)]:
        stack.appendleft((i[0],i[1],m))
    for i in G1[(a,c)]:
      if not visited[(a,c)]:
        stack.append((i[0],i[1],m+1))
    visited[(a,c)]=True
  return -1

print(BFS(0))


      
    

Fixed submission:
from collections import defaultdict,deque
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
N,M=map(int,input().split())
if M==0:
  print(-1)
  exit()
G=defaultdict(set)
for i in range(M):
  a,b,c=map(int,input().split())
  G[a+(c<<30)].add(b+(c<<30))
  G[b+(c<<30)].add(a+(c<<30))
  G[a].add(a+(c<<30))
  G[b].add(b+(c<<30))
  G[a+(c<<30)].add(a)
  G[b+(c<<30)].add(b)
def BFS(x):
  d={}
  for k in G.keys():
    d[k]=float("inf")
  stack=deque([(x,0)])
  if x not in d:
    return -1
  while stack:
    s,m=stack.popleft()
    if s==N:
      return m
    if d[s]>m:
      d[s]=m
      if s>=(1<<30):
        for i in G[s]:
          if d[i]>10**30:
            stack.appendleft((i,m))
      else: 
        for i in G[s]:
          if d[i]>10**30:
            stack.append((i,m+1))
  return -1

print(BFS(1))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict,deque
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
G0=defaultdict(set)
G1=defaultdict(set)
Comps=[[] for i in range(N)]
for i in range(M):
  a,b,c=map(int,input().split())
  G0[(a-1,c-1)].add((b-1,c-1))
  G0[(a-1,c-1)].add((a-1,-1))
  G0[(b-1,c-1)].add((b-1,-1))
  G0[(b-1,c-1)].add((a-1,c-1))
  Comps[a-1].append(c-1)
  Comps[b-1].append(c-1)
for i in range(N):
  for c in Comps[i]:
    G1[(i,-1)].add((i,c))
def BFS(x):
  visited=defaultdict(bool)
  stack=deque([(x,-1,0)])
  while stack:
    a,c,m=stack.popleft()
    if visited[(a,c)]:
      continue
    if a==N-1 and c==-1:
      return m
    for i in G0[(a,c)]:
      if not visited[i[0]]:
        stack.appendleft((i[0],i[1],m))
    for i in G1[(a,c)]:
      if not visited[i[0]]:
        stack.append((i[0],i[1],m+1))
    visited[(a,c)]=True
  return -1

print(BFS(0))


      
    

Fixed submission:
from collections import defaultdict,deque
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
N,M=map(int,input().split())
if M==0:
  print(-1)
  exit()
G=defaultdict(set)
for i in range(M):
  a,b,c=map(int,input().split())
  G[a+(c<<30)].add(b+(c<<30))
  G[b+(c<<30)].add(a+(c<<30))
  G[a].add(a+(c<<30))
  G[b].add(b+(c<<30))
  G[a+(c<<30)].add(a)
  G[b+(c<<30)].add(b)
def BFS(x):
  d={}
  for k in G.keys():
    d[k]=float("inf")
  stack=deque([(x,0)])
  if x not in d:
    return -1
  while stack:
    s,m=stack.popleft()
    if s==N:
      return m
    if d[s]>m:
      d[s]=m
      if s>=(1<<30):
        for i in G[s]:
          if d[i]>10**30:
            stack.appendleft((i,m))
      else: 
        for i in G[s]:
          if d[i]>10**30:
            stack.append((i,m+1))
  return -1

print(BFS(1))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict,deque
N,M=map(int,input().split())
G0=defaultdict(set)
G1=defaultdict(set)
Comps=[[] for i in range(N)]
for i in range(M):
  a,b,c=map(int,input().split())
  G0[(a-1,c-1)].add((b-1,c-1))
  G0[(a-1,c-1)].add((a-1,-1))
  G0[(b-1,c-1)].add((b-1,-1))
  G0[(b-1,c-1)].add((a-1,c-1))
  Comps[a-1].append(c-1)
  Comps[b-1].append(c-1)
for i in range(N):
  for c in Comps[i]:
    G1[(i,-1)].add((i,c))
def BFS(x):
  visited=defaultdict(bool)
  stack=deque([(x,-1,0)])
  while stack:
    a,c,m=stack.popleft()
    if visited[(a,c)]:
      continue
    if a==N-1 and c==-1:
      return m
    visited[(a,c)]=True
    for i in G0[(a,c)]:
      if not visited[i]:
        stack.appendleft((i[0],i[1],m))
    for i in G1[(a,c)]:
      if not visited[i]:
        stack.append((i[0],i[1],m+1))
  return -1

print(BFS(0))

      
    

Fixed submission:
from collections import defaultdict,deque
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
N,M=map(int,input().split())
if M==0:
  print(-1)
  exit()
G=defaultdict(set)
for i in range(M):
  a,b,c=map(int,input().split())
  G[a+(c<<30)].add(b+(c<<30))
  G[b+(c<<30)].add(a+(c<<30))
  G[a].add(a+(c<<30))
  G[b].add(b+(c<<30))
  G[a+(c<<30)].add(a)
  G[b+(c<<30)].add(b)
def BFS(x):
  d={}
  for k in G.keys():
    d[k]=float("inf")
  stack=deque([(x,0)])
  if x not in d:
    return -1
  while stack:
    s,m=stack.popleft()
    if s==N:
      return m
    if d[s]>m:
      d[s]=m
      if s>=(1<<30):
        for i in G[s]:
          if d[i]>10**30:
            stack.appendleft((i,m))
      else: 
        for i in G[s]:
          if d[i]>10**30:
            stack.append((i,m+1))
  return -1

print(BFS(1))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict,deque
N,M=map(int,input().split())
G0=defaultdict(set)
G1=defaultdict(set)
Comps=[[] for i in range(N)]
for i in range(M):
  a,b,c=map(int,input().split())
  G0[(a-1,c-1)].add((b-1,c-1))
  G0[(a-1,c-1)].add((a-1,-1))
  G0[(b-1,c-1)].add((b-1,-1))
  G0[(b-1,c-1)].add((a-1,c-1))
  Comps[a-1].append(c-1)
  Comps[b-1].append(c-1)
for i in range(N):
  for c in Comps[i]:
    G1[(i,-1)].add((i,c))
def BFS(x):
  visited=defaultdict(bool)
  stack=deque([(x,-1,0)])
  while stack:
    a,c,m=stack.popleft()
    if visited[(a,c)]:
      continue
    if a==N-1 and c==-1:
      return m
    visited[(a,c)]=True
    for i in G0[(a,c)]:
      if not visited[i]:
        stack.appendleft((i[0],i[1],m))
    for i in G1[(a,c)]:
      if not visited[i]:
        stack.append((i[0],i[1],m+1))
  return -1

print(BFS(0))

      
    

Fixed submission:
from collections import defaultdict,deque
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
N,M=map(int,input().split())
if M==0:
  print(-1)
  exit()
G=defaultdict(set)
for i in range(M):
  a,b,c=map(int,input().split())
  G[a+(c<<30)].add(b+(c<<30))
  G[b+(c<<30)].add(a+(c<<30))
  G[a].add(a+(c<<30))
  G[b].add(b+(c<<30))
  G[a+(c<<30)].add(a)
  G[b+(c<<30)].add(b)
def BFS(x):
  d={}
  for k in G.keys():
    d[k]=float("inf")
  stack=deque([(x,0)])
  if x not in d:
    return -1
  while stack:
    s,m=stack.popleft()
    if s==N:
      return m
    if d[s]>m:
      d[s]=m
      if s>=(1<<30):
        for i in G[s]:
          if d[i]>10**30:
            stack.appendleft((i,m))
      else: 
        for i in G[s]:
          if d[i]>10**30:
            stack.append((i,m+1))
  return -1

print(BFS(1))