Problem: 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.

Examples

Input

3 3
1 2 1
2 3 1
3 1 2


Output

1


Input

8 11
1 3 1
1 4 2
2 3 1
2 5 1
3 4 3
3 6 3
3 7 3
4 8 4
5 6 1
6 7 5
7 8 5


Output

2


Input

2 0


Output

-1

Solution (in PYTHON3):

Solution:
def dijkstra_heap(s,edge,mask):
    dist = defaultdict(lambda: float("inf"))
    q = [s]  # 0 が会社に属していない状態
    dist[s] = 0
    d = 0; q0 = []; q1 = []
    while q:
        for x in q:
            if x & mask == 0:
                for y in edge[x]:
                    if dist[y[1]] <= d + y[0]:
                        continue
                    dist[y[1]] = d + y[0]
                    q1.append(y[1])
            else:
                for y in edge[x]:
                    if dist[y[1]] <= d+ y[0]:
                        continue
                    dist[y[1]] = d+ y[0]
                    q0.append(y[1])
        if q0:
            q = q0
            q0 = []
            continue
        q = q1
        q1 = []
        d += 1
    return dist

def examE(inf):
    N, M = LI()
    edge = defaultdict(list)
    # edge[i] : iから出る道の[重み,行先]の配列
    L = 32
    Mask = (1 << L) - 1
    for i in range(M):
        p, q, c = map(int, input().split())
        p -=1; q -=1
        p <<= L
        q <<= L
        #同じ路線だとコスト０ 乗るときだけコスト１
        edge[p].append((1,p + c))
        edge[p + c].append((0,p))
        edge[q].append((1,q + c))
        edge[q + c].append((0,q))
        edge[p + c].append((0,q + c))
        edge[q + c].append((0,p + c))
    start = 0
    goal = (N-1) << L
    res = dijkstra_heap(start, edge, Mask)
#    print(res)
    ans = res[goal]
    if ans == inf:
        ans = -1
    print(ans)


import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examE(inf)