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 = 'import sys\ninput = lambda: sys.stdin.readline().rstrip()\nfrom collections import deque\nN, M = map(int, input().split())\nX = []\nC = [set() for _ in range(N)]\nfor _ in range(M):\n    p, q, c = [int(a) - 1 for a in input().split()]\n    X.append((p, q, c))\n    C[p].add(c)\n    C[q].add(c)\nfor i, c in enumerate(C):\n    C[i] = list(c)\n\nI = [N]\nD = [{} for _ in range(N)]\nfor i, c in enumerate(C):\n    for j, a in enumerate(c):\n        D[i][a] = I[-1] + j\n    I.append(I[-1] + len(c))\n\nT = I[-1]\nE = [[] for _ in range(T)]\nfor p, q, c in X:\n    E[D[p][c]].append((D[q][c], 0))\n    E[D[q][c]].append((D[p][c], 0))\nfor i, c in enumerate(C):\n    for j, a in enumerate(c):\n        E[i].append((D[i][a], 1))\n        E[D[i][a]].append((i, 1))\n\ndef BFS01(n, E, i0=0):\n    Q = deque([i0])\n    D = [-1] * n\n    D[i0] = 0\n    while Q:\n        x = Q.popleft()\n        for y, w in E[x]:\n            if w:\n                if D[y] == -1:\n                    D[y] = D[x] + 1\n                    Q.append(y)\n            else:\n                if D[y] == -1 or D[y] < D[x]:\n                    D[y] = D[x]\n                    Q.appendleft(y)\n    return D\n\nD = BFS01(T, E, 0)\nprint(D[N-1] // 2)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 15057