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:
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)