# Original solution
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**7) 
 
def li(): return list(map(int, stdin.readline().split()))
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return list(map(float, stdin.readline().split()))
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from heapq import heappush, heappop
from collections import defaultdict

def dijkstra(graph, start, INF, num2node, destination) -> int:
    n = len(graph)
    dist = [INF]*n
    visited = [False]*n
    
    dist[start] = 0
    que = [(dist[start], start)]
    
    while que:
        cost, cur = heappop(que)
        
        if visited[cur]:
            continue
        
        if num2node[cur][0] == destination:
            return cost
        
        visited[cur] = True
        
        for nextnode, edgecost in graph[cur]:
            nextcost = cost + edgecost
            if nextcost < dist[nextnode]:
                dist[nextnode] = nextcost
                heappush(que, (nextcost, nextnode))
      
    return INF

def get_nodenum(station, company, keyset, node2num):
    if (station, company) not in keyset:
        keyset.add((station, company))
        keyslen = len(keyset)-1
        node2num.update({(station, company): keyslen})
        
        return keyslen
    
    else:
        return node2num[(station, company)]
    

n,m = li()

graph = defaultdict(set)
node2num = {}
num2node = {}
keyset = set()

for _ in range(m):
    p,q,c = li()

    # ノードの登録
    pc_nodenum = get_nodenum(p,c,keyset,node2num)
    qc_nodenum = get_nodenum(q,c,keyset,node2num)
    
    pz_nodenum = get_nodenum(p,0,keyset,node2num)
    qz_nodenum = get_nodenum(q,0,keyset,node2num)
    

    # 隣接リストの更新
    graph[pc_nodenum].add((qc_nodenum, 0))
    graph[qc_nodenum].add((pc_nodenum, 0))
    
    graph[pc_nodenum].add((pz_nodenum, 0))
    graph[qc_nodenum].add((qz_nodenum, 0))
    
    graph[pz_nodenum].add((pc_nodenum, 1))
    graph[qz_nodenum].add((qc_nodenum, 1))
    
INF = 1<<62
start = get_nodenum(1, 0, keyset, node2num)
if m == 0:
    print((-1))
    
else:
    num2node = {ni: (stati, compi) for (stati, compi), ni in list(node2num.items())}
    del node2num
    
    ans = dijkstra(graph, start, INF, num2node, n)
    
    print((-1 if ans == INF else ans))
        

# Optimized solution
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return list(map(int, stdin.readline().split()))
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return list(map(float, stdin.readline().split()))
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import defaultdict, deque

# 入力・隣接リスト作成
n,m = li()
graph = defaultdict(set)
geta = pow(10,7)

for _ in range(m):
    p,q,c = li()
    
    graph[p + c*geta].add(q + c*geta)
    graph[q + c*geta].add(p + c*geta)
    
    graph[p + c*geta].add(p)
    graph[q + c*geta].add(q)
    
    graph[p].add(p + c*geta)
    graph[q].add(q + c*geta)
    
que = deque()
que.append((0, 1))
visited = set()

ans = -1

while que:
    (cost, node) = que.popleft()
    
    if node in visited:
        continue
    
    elif node % geta == n:
        ans = cost
        break
    
    visited.add(node)
    
    
    for nex in graph[node]:
        if nex in visited:
            continue
        
        elif node <= n and nex > n:
            que.append((cost+1, nex))
            
        else:
            que.appendleft((cost, nex))
    
print(ans)