### BUGGY CODE ###

N,M = map(int, input().split())
if M == 0:
    print(-1)
    exit()
pqcs = [list(map(int, input().split())) for _ in range(M)]
c_max = max(list(map(lambda x: x[2],pqcs)))
node_num = (c_max+1)*N
#unsearached_nodes = list(range(node_num))#0～N-1(n-1)が乗換経由ノード/路線iの駅nは3*i+(n-1)番ノード
unsearched_nodes = [c*10**6+s+1 for s in range(N) for c in range(c_max+1)]
#opt_nodes = [-1]*node_num
#distance = [float('inf')]*node_num
#distance[0] = 0
distance = {c*10**6+s+1: float('inf') for s in range(N) for c in range(c_max+1)}
distance[1] = 0
#edges = [[float('inf')]*node_num for _ in range(node_num)]
#辺へ重み付け
edges = {}
for p,q,c in pqcs:
	edge = {}
	edge[c*10**6+q] = 0
	edge[p] = 0
	edges.setdefault(c*10**6+p, {})
	edges[c*10**6+p].update(edge)
	edge = {}
	edge[c*10**6+p] = 0
	edge[q] = 0
	edges.setdefault(c*10**6+q, {})
	edges[c*10**6+q].update(edge)
	edge = {}
	edge[c*10**6+p] = 1
	edges.setdefault(p, {})
	edges[p].update(edge)
	edge = {}
	edge[c*10**6+q] = 1
	edges.setdefault(q, {})
	edges[q].update(edge)

while (distance[N] == float('inf')):
    temp_min_dist = float('inf')
    for unsearched_ind in unsearched_nodes:
        if temp_min_dist > distance[unsearched_ind]:
            temp_min_dist = distance[unsearched_ind]
            target_min_ind = unsearched_ind
    #if temp_min_dist == float('inf'):
        #break
    unsearched_nodes.remove(target_min_ind)
    target_node = edges[target_min_ind]
   
    for key, value in target_node.items():
    	if distance[key] > distance[target_min_ind] + value:
    		distance[key] = distance[target_min_ind] + value
    		#opt_nodes[key] = target_min_ind

print(distance[N] if distance[N] != float('inf') else -1)

### FIXED CODE ###

from collections import deque
N, M = map(int, input().split())
F_C_of_S = [{} for i in range(N)]
#Companies of Station
C_of_S = {}

#def Union-find
parent = [-1]*M
def root(x):
	if (parent[x] < 0): return x
	else:
		parent[x] = y = root(parent[x])
		return y

def unite(x, y):
	px = root(x)
	py = root(y)
	if (px == py): return False
	if (parent[px] > parent[py]):
		px = root(y)
		py = root(x)
	parent[px] += parent[py]
	parent[py] = px
	return True


#Union-find
pqcs = []
for i in range(M):
	p, q, c = map(int, input().split())
	p -= 1; q -= 1;
	pqcs += [(p, q, c)]
	
	#The first
	if not c in F_C_of_S[p]: F_C_of_S[p][c] = i
	#else
	else: unite(F_C_of_S[p][c], i)
	C_of_S.setdefault(p, set()).add(c)
	
	#The first
	if not (c in F_C_of_S[q]):F_C_of_S[q][c] = i
	#else
	else: unite(F_C_of_S[q][c], i)
	C_of_S.setdefault(q, set()).add(c)

#stations of company
S_of_C = {}
for i in range(M):
	p, q, c = pqcs[i]
	c_set = S_of_C.setdefault(root(i), set())
	c_set.add(p)
	c_set.add(q)


Q = deque([(0, 0, 0)])
#cost to go to the stations from station_0
dist = [float('inf')]*N
dist[0] = 0

gdist = [float('inf')]*M

while Q:
	cost, v, flag = Q.popleft()
	
	if not (flag):#(flag == 0) then gdist_update
		if (dist[v] < cost) or (v not in C_of_S):
			continue
		for l in F_C_of_S[v].values():
			l = root(l)
			if (cost < gdist[l]):
				gdist[l] = cost
				Q.appendleft((cost, l, 1))
	
	else:#(flag == 1) then dist_update
		if (gdist[v] < cost) or (v not in S_of_C):
			continue
		for s in S_of_C[v]:
			if (cost+1 < dist[s]):
				dist[s] = cost+1
				Q.append((cost+1, s, 0))

print(dist[N - 1] if dist[N - 1] < float('inf') else -1)