output_description: Print the minimum required fare. If it is impossible to get to station N by
  subway, print `-1` instead.
  
  * * *
input_description: 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
attempt: from subprocess import *
  
  call(
      (
          "pypy3",
          "-c",
          """
  def main():
    from heapq import heappush,heappop,heapify
    inf=2**31-1
    n,m,*t=map(int,open(0).read().split())
    z=[]
    for a,b,c in zip(t[::3],t[1::3],t[2::3]):
      z.extend([a,b,a+n*c,b+n*c])
    z={i:v for v,i in enumerate(sorted(set(z)))}
    try:
      z[1]
    except:
      print(-1)
      exit()
    edge=[[]for _ in range(len(z))]
    d={}
    l=[]
    for a,b,c in zip(t[::3],t[1::3],t[2::3]):
      if b<a:a,b=b,a
      i,j,x,y=z[a],z[b],z[a+n*c],z[b+n*c]
      if b==n:
        l.append(y)
      edge[i].append((1,x))
      edge[j].append((1,y))
      edge[x].extend([(0,i),(0,y)])
      edge[y].extend([(0,j),(0,x)])
    used=[False]+[True]*~-len(z)
    d=[0]+[inf]*~-len(z)
    edgelist=edge[0]
    heapify(edgelist)
    while edgelist:
      m=heappop(edgelist)
      if not used[m[1]]:
        continue
      d[m[1]]=m[0]
      used[m[1]]=False
      for e in edge[m[1]]:
        if used[e[1]]:
          heappush(edgelist,(e[0]+m[0],e[1]))
    a=min([d[i]for i in l]or[inf])
    print([a,-1][a==inf])
  if __name__=='__main__':
    main()
  """,
      )
  )
  
problem_description: 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.
samples: [{"input": "3 3\n    1 2 1\n    2 3 1\n    3 1 2", "output": "1\n    \n\nUse company 1's lines: 1 \u2192 2 \u2192 3. The fare is 1 yen.\n\n* * *"}, {"input": "8 11\n    1 3 1\n    1 4 2\n    2 3 1\n    2 5 1\n    3 4 3\n    3 6 3\n    3 7 3\n    4 8 4\n    5 6 1\n    6 7 5\n    7 8 5", "output": "2\n    \n\nFirst, use company 1's lines: 1 \u2192 3 \u2192 2 \u2192 5 \u2192 6. Then, use company 5's lines:\n6 \u2192 7 \u2192 8. The fare is 2 yen.\n\n* * *"}, {"input": "2 0", "output": "-1"}]