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: n, m = map(int, input().split())
  s = [[] for i in range(n + 1)]
  for j in range(m):
      p, q, c = map(int, input().split())
      s[p].append([q, c])
      s[q].append([p, c])
  l = [-1] * (n + 1)
  l[1] = 0
  d = [[1, 0, 0]]
  while not l[-1] or d:
      a, b, c = d.pop(0)
      for i, j in s[a]:
          if l[i] == -1:
              if j == b:
                  l[i] = c
                  d.insert(0, [i, b, c])
              else:
                  l[i] = c + 1
                  d.append([i, j, c + 1])
  print(l[-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"}]