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 heapq import heappop, heappush
  N,M = map(int, input().split())
  edges = [[] for _ in range(N)]
  cs = set{}
  for i in range(M):
  	p,q,c = map(int, input().split())
  	cs += c
  	edges[p-1] += [[q-1, c]]
  	edges[q-1] += [[p-1, c]]
  c_num = len(cs)
  distance = [[float('inf')]*(c_num+1) for _ in range(N)]
  distance[0][0] = 0
  min_distance = [float('inf')]*N
  min_distance[0] = 0
  Q = [[0, 0]]
  
  while Q:
  	s_now,c_now = heappop(Q)
  	for t, c in edges[s_now]:
  		if min_distance[t] > distance[s_now][c_now] + (c_now != c):
  			distance[t][c] = distance[s_now][c_now] + (c_now != c)
  			min_distance[t] = distance[t][c]
  			heappush(Q, [t, c])
  print(min_distance[N-1] if min_distance[N-1] != float('inf') else -1)
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"}]