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: class UnionFindVerSize:
      def __init__(self, init):
          """N個のノードのUnion-Find木を作成する"""
          # 親の番号を格納する。自分が親だった場合は、自分の番号になり、それがそのグループの番号になる
          self._parent = [n for n in range(0, len(init))]
          # グループのサイズ（個数）
          self._size = [1] * len(init)
          self._dict = {key: 0 for key in init}
          for i in range(len(init)):
              v = init[i]
              self._dict[v] = i
  
      def find_root(self, x, key):
          """xの木の根(xがどのグループか)を求める"""
          if key == 1:
              x = self._dict[x]
          if self._parent[x] == x:
              return x
          self._parent[x] = self.find_root(self._parent[x], 0)  # 縮約
          return self._parent[x]
  
      def unite(self, x, y):
          """xとyの属するグループを併合する"""
          x = self._dict[x]
          y = self._dict[y]
          gx = self.find_root(x, 0)
          gy = self.find_root(y, 0)
          if gx == gy:
              return
  
          # 小さい方を大きい方に併合させる（木の偏りが減るので）
          if self._size[gx] < self._size[gy]:
              self._parent[gx] = gy
              self._size[gy] += self._size[gx]
          else:
              self._parent[gy] = gx
              self._size[gx] += self._size[gy]
  
      def get_size(self, x):
          x = self._dict[x]
          """ xが属するグループのサイズ（個数）を返す """
          return self._size[self.find_root(x, 0)]
  
      def is_same_group(self, x, y):
          x = self._dict[x]
          y = self._dict[y]
          """ xとyが同じ集合に属するか否か """
          return self.find_root(x, 0) == self.find_root(y, 0)
  
      def calc_group_num(self):
          """グループ数を計算して返す"""
          N = len(self._parent)
          ans = 0
          for i in range(N):
              if self.find_root(i, 0) == i:
                  ans += 1
          return ans
  
  
  import sys
  
  input = sys.stdin.readline
  
  N, M = map(int, input().split())
  company = {}
  cedge = {}
  node = N
  edge = {i: [] for i in range(N)}
  for i in range(M):
      u, v, c = map(int, input().split())
      edge[u - 1].append((v - 1, 1))
      edge[v - 1].append((u - 1, 1))
      if c - 1 not in company:
          company[c - 1] = []
          cedge[c - 1] = []
      company[c - 1].append(u - 1)
      company[c - 1].append(v - 1)
      cedge[c - 1].append((u - 1, v - 1))
  
  for i in company:
      uf = UnionFindVerSize(company[i])
      for u, v in cedge[i]:
          uf.unite(u, v)
      data = {}
      for v in company[i]:
          p = uf.find_root(v, 1)
          if p not in data:
              data[p] = []
          data[p].append(v)
      for p in data:
          edge[node] = []
          for v in data[p]:
              edge[v].append((node, 0))
              edge[node].append((v, 1))
          node += 1
  
  from collections import deque
  
  dist = [10**20] * node
  dist[0] = 0
  que = deque([(0, 0)])
  while que:
      v, d = que.popleft()
      for nv, c in edge[v]:
          if dist[nv] > d + c:
              if c == 1:
                  dist[nv] = d + c
                  que.append((nv, d + c))
              else:
                  dist[nv] = d + c
                  que.appendleft((nv, d + c))
  
  
  ans = dist[N - 1]
  print(ans if ans != 10**20 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"}]