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: import sys
  
  input = sys.stdin.readline
  from scipy.sparse import csr_matrix
  from scipy.sparse.csgraph import dijkstra
  
  """
  (駅、会社)を頂点にグラフを持つ。頂点数O(M)。
  そのまま辺を貼ると辺が多くなりすぎる。
  (駅、会社) -> (駅、無属性) -> (駅、会社)
  """
  
  N, M = map(int, input().split())
  PQC = [[int(x) for x in input().split()] for _ in range(M)]
  
  V = set((x, 0) for x in range(1, N + 1))
  V |= set((p, c) for p, q, c in PQC)
  V |= set((q, c) for p, q, c in PQC)
  V = list(V)
  v_to_i = {v: i for i, v in enumerate(V)}
  
  # グラフを作成
  rows = []
  cols = []
  wt = []
  for i, (p, c) in enumerate(V):
      if c != 0:
          j = v_to_i[(p, 0)]
          rows.append(i)
          cols.append(j)
          wt.append(1)
  for p, q, c in PQC:
      i = v_to_i[(p, c)]
      j = v_to_i[(q, c)]
      rows.append(i)
      cols.append(j)
      wt.append(0)
  
  graph = csr_matrix((wt, (rows, cols)), (len(V), len(V)))
  
  start = v_to_i[(1, 0)]
  goal = v_to_i[(N, 0)]
  
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"}]