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.

-----Constraints-----
 - 2 \leq N \leq 10^5
 - 0 \leq M \leq 2×10^5
 - 1 \leq p_i \leq N (1 \leq i \leq M)
 - 1 \leq q_i \leq N (1 \leq i \leq M)
 - 1 \leq c_i \leq 10^6 (1 \leq i \leq M)
 - p_i \neq q_i (1 \leq i \leq M)

-----Input-----
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

-----Output-----
Print the minimum required fare. If it is impossible to get to station N by subway, print -1 instead.

-----Sample Input-----
3 3
1 2 1
2 3 1
3 1 2

-----Sample Output-----
1

Use company 1's lines: 1 → 2 → 3. The fare is 1 yen.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'class UnionFindVerSize():\n    def __init__(self,init):\n        """ N個のノードのUnion-Find木を作成する """\n        # 親の番号を格納する。自分が親だった場合は、自分の番号になり、それがそのグループの番号になる\n        self._parent = [n for n in range(0, len(init))]\n        # グループのサイズ（個数）\n        self._size = [1] * len(init)\n        self._dict ={key:0 for key in init}\n        for i in range(len(init)):\n            v=init[i]\n            self._dict[v]=i\n\n    def find_root(self, x,key):\n        """ xの木の根(xがどのグループか)を求める """\n        if key==1:\n            x=self._dict[x]\n        if self._parent[x] == x: return x\n        self._parent[x] = self.find_root(self._parent[x],0) # 縮約\n        return self._parent[x]\n\n    def unite(self, x, y):\n        """ xとyの属するグループを併合する """\n        x=self._dict[x]\n        y=self._dict[y]\n        gx = self.find_root(x,0)\n        gy = self.find_root(y,0)\n        if gx == gy: return\n\n        # 小さい方を大きい方に併合させる（木の偏りが減るので）\n        if self._size[gx] < self._size[gy]:\n            self._parent[gx] = gy\n            self._size[gy] += self._size[gx]\n        else:\n            self._parent[gy] = gx\n            self._size[gx] += self._size[gy]\n\n    def get_size(self, x):\n        x=self._dict[x]\n        """ xが属するグループのサイズ（個数）を返す """\n        return self._size[self.find_root(x,0)]\n\n    def is_same_group(self, x, y):\n        x=self._dict[x]\n        y=self._dict[y]\n        """ xとyが同じ集合に属するか否か """\n        return self.find_root(x,0) == self.find_root(y,0)\n\n    def calc_group_num(self):\n        """ グループ数を計算して返す """\n        N = len(self._parent)\n        ans = 0\n        for i in range(N):\n            if self.find_root(i,0) == i:\n                ans += 1\n        return ans\n\nimport sys\n\ninput=sys.stdin.readline\n\nN,M=map(int,input().split())\ncompany={}\ncedge={}\nnode=N\nedge={i:[] for i in range(N)}\nfor i in range(M):\n    u,v,c=map(int,input().split())\n    edge[u-1].append((v-1,1))\n    edge[v-1].append((u-1,1))\n    if c-1 not in company:\n        company[c-1]=[]\n        cedge[c-1]=[]\n    company[c-1].append(u-1)\n    company[c-1].append(v-1)\n    cedge[c-1].append((u-1,v-1))\n\nfor i in company:\n    uf=UnionFindVerSize(company[i])\n    for u,v in cedge[i]:\n        uf.unite(u,v)\n    data={}\n    for v in company[i]:\n        p=uf.find_root(v,1)\n        if p not in data:\n            data[p]=[]\n        data[p].append(v)\n    for p in data:\n        edge[node]=[]\n        for v in data[p]:\n            edge[v].append((node,0))\n            edge[node].append((v,1))\n        node+=1\n\nfrom collections import deque\ndist=[10**20]*node\ndist[0]=0\nque=deque([(0,0)])\nwhile que:\n    v,d=que.popleft()\n    for nv,c in edge[v]:\n        if dist[nv]>d+c:\n            if c==1:\n                dist[nv]=d+c\n                que.append((nv,d+c))\n            else:\n                dist[nv]=d+c\n                que.appendleft((nv,d+c))\n\n\nans=dist[N-1]\nprint(ans if ans!=10**20 else -1)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 18011