import sys

input = sys.stdin.readline

from collections import defaultdict



"""

(駅、会社)を頂点にグラフを持つ。頂点数O(M)。

そのまま辺を貼ると辺が多くなりすぎる。

(駅、会社) -> (駅、無属性) -> (駅、会社)

"""



L = 32

mask = (1 << L) - 1

N,M = list(map(int,input().split()))

graph = defaultdict(list)

for _ in range(M):

    p,q,c = list(map(int,input().split()))

    p <<= L

    q <<= L

    graph[p].append(p+c)

    graph[p+c].append(p)

    graph[q].append(q+c)

    graph[q+c].append(q)

    graph[p+c].append(q+c)

    graph[q+c].append(p+c)



INF = 10 ** 9

dist = defaultdict(lambda: INF)



start = 1 << L

goal = N << L



q = [start] # 0 が会社に属していない状態

dist[start] = 0

d = 0

q0 = []

q1 = []

while q:

    for x in q:

        if x & mask == 0:

            for y in graph[x]:

                if dist[y] <= d + 1:

                    continue

                dist[y] = d + 1

                q1.append(y)

        else:

            for y in graph[x]:

                if dist[y] <= d:

                    continue

                dist[y] = d

                q0.append(y)

    if q0:

        q = q0

        q0 = []

        continue

    q = q1

    q1 = []

    d += 1



answer = dist[goal]

if answer == INF:

    answer = -1

print(answer)
import sys

read = sys.stdin.buffer.read

readline = sys.stdin.buffer.readline

readlines = sys.stdin.buffer.readlines



from collections import deque



N,M = list(map(int,readline().split()))

if M == 0:

    print((-1))

    exit()

m = list(map(int,read().split()))

P,Q,C = list(zip(*list(zip(m,m,m))))



V = []

V += [p<<32 for p in range(1,N+1)]

V += [(p<<32)+c for p,c in zip(P,C)]

V += [(q<<32)+c for q,c in zip(Q,C)]

V = set(V)

label = {x:i for i,x in enumerate(V)}

start = label[1<<32]

goal = label[N<<32]



N = len(V)

graph = [[] for _ in range(N)]

for p,q,c in zip(P,Q,C):

    v0 = label[p<<32]; v1 = label[(p<<32)+c]

    w0 = label[q<<32]; w1 = label[(q<<32)+c]

    graph[v0].append((v1,1))

    graph[w0].append((w1,1))

    graph[v1].append((v0,0))

    graph[w1].append((w0,0))

    graph[v1].append((w1,0))

    graph[w1].append((v1,0))



INF = 10 ** 10

dist = [INF] * N

dist[start] = 0

q = deque([(0,start)])

while q:

    dv,v = q.popleft()

    for w,cost in graph[v]:

        dw = dv + cost

        if dw >= dist[w]:

            continue

        dist[w] = dw

        if not cost:

            q.appendleft((dw,w))

        else:

            q.append((dw,w))



answer = dist[goal]

if answer == INF:

    answer = -1

print(answer)
import sys

input = sys.stdin.readline
from collections import defaultdict

"""
(駅、会社)を頂点にグラフを持つ。頂点数O(M)。
そのまま辺を貼ると辺が多くなりすぎる。
(駅、会社) -> (駅、無属性) -> (駅、会社)
"""
L = 32
mask = (1 << L) - 1
N, M = list(map(int, input().split()))
graph = defaultdict(list)
for _ in range(M):
    p, q, c = list(map(int, input().split()))
    p <<= L
    q <<= L
    graph[p].append(p + c)
    graph[p + c].append(p)
    graph[q].append(q + c)
    graph[q + c].append(q)
    graph[p + c].append(q + c)
    graph[q + c].append(p + c)
INF = 10**9
dist = defaultdict(lambda: INF)
start = 1 << L
goal = N << L
q = [start]  # 0 が会社に属していない状態
dist[start] = 0
d = 0
q0 = []
q1 = []
while q:
    for x in q:
        if x & mask == 0:
            for y in graph[x]:
                if dist[y] <= d + 1:
                    continue
                dist[y] = d + 1
                q1.append(y)
        else:
            for y in graph[x]:
                if dist[y] <= d:
                    continue
                dist[y] = d
                q0.append(y)
    if q0:
        q = q0
        q0 = []
        continue
    q = q1
    q1 = []
    d += 1
answer = dist[goal]
if answer == INF:
    answer = -1
print(answer)

import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque

N, M = list(map(int, readline().split()))
if M == 0:
    print((-1))
    exit()
m = list(map(int, read().split()))
P, Q, C = list(zip(*list(zip(m, m, m))))
V = []
V += [p << 32 for p in range(1, N + 1)]
V += [(p << 32) + c for p, c in zip(P, C)]
V += [(q << 32) + c for q, c in zip(Q, C)]
V = set(V)
label = {x: i for i, x in enumerate(V)}
start = label[1 << 32]
goal = label[N << 32]
N = len(V)
graph = [[] for _ in range(N)]
for p, q, c in zip(P, Q, C):
    v0 = label[p << 32]
    v1 = label[(p << 32) + c]
    w0 = label[q << 32]
    w1 = label[(q << 32) + c]
    graph[v0].append((v1, 1))
    graph[w0].append((w1, 1))
    graph[v1].append((v0, 0))
    graph[w1].append((w0, 0))
    graph[v1].append((w1, 0))
    graph[w1].append((v1, 0))
INF = 10**10
dist = [INF] * N
dist[start] = 0
q = deque([(0, start)])
while q:
    dv, v = q.popleft()
    for w, cost in graph[v]:
        dw = dv + cost
        if dw >= dist[w]:
            continue
        dist[w] = dw
        if not cost:
            q.appendleft((dw, w))
        else:
            q.append((dw, w))
answer = dist[goal]
if answer == INF:
    answer = -1
print(answer)

-input = sys.stdin.readline -from collections import defaultdict +read = sys.stdin.buffer.read +readline = sys.stdin.buffer.readline +readlines = sys.stdin.buffer.readlines +from collections import deque -""" -(駅、会社)を頂点にグラフを持つ。頂点数O(M)。 -そのまま辺を貼ると辺が多くなりすぎる。 -(駅、会社) -> (駅、無属性) -> (駅、会社) -""" -L = 32 -mask = (1 << L) - 1 -N, M = list(map(int, input().split())) -graph = defaultdict(list) -for _ in range(M): -    p, q, c = list(map(int, input().split())) -    p <<= L -    q <<= L -    graph[p].append(p + c) -    graph[p + c].append(p) -    graph[q].append(q + c) -    graph[q + c].append(q) -    graph[p + c].append(q + c) -    graph[q + c].append(p + c) -INF = 10**9 -dist = defaultdict(lambda: INF) -start = 1 << L -goal = N << L -q = [start]  # 0 が会社に属していない状態 +N, M = list(map(int, readline().split())) +if M == 0: +    print((-1)) +    exit() +m = list(map(int, read().split())) +P, Q, C = list(zip(*list(zip(m, m, m)))) +V = [] +V += [p << 32 for p in range(1, N + 1)] +V += [(p << 32) + c for p, c in zip(P, C)] +V += [(q << 32) + c for q, c in zip(Q, C)] +V = set(V) +label = {x: i for i, x in enumerate(V)} +start = label[1 << 32] +goal = label[N << 32] +N = len(V) +graph = [[] for _ in range(N)] +for p, q, c in zip(P, Q, C): +    v0 = label[p << 32] +    v1 = label[(p << 32) + c] +    w0 = label[q << 32] +    w1 = label[(q << 32) + c] +    graph[v0].append((v1, 1)) +    graph[w0].append((w1, 1)) +    graph[v1].append((v0, 0)) +    graph[w1].append((w0, 0)) +    graph[v1].append((w1, 0)) +    graph[w1].append((v1, 0)) +INF = 10**10 +dist = [INF] * N -d = 0 -q0 = [] -q1 = [] +q = deque([(0, start)]) -    for x in q: -        if x & mask == 0: -            for y in graph[x]: -                if dist[y] <= d + 1: -                    continue -                dist[y] = d + 1 -                q1.append(y) +    dv, v = q.popleft() +    for w, cost in graph[v]: +        dw = dv + cost +        if dw >= dist[w]: +            continue +        dist[w] = dw +        if not cost: +            q.appendleft((dw, w)) -            for y in graph[x]: -                if dist[y] <= d: -                    continue -                dist[y] = d -                q0.append(y) -    if q0: -        q = q0 -        q0 = [] -        continue -    q = q1 -    q1 = [] -    d += 1 +            q.append((dw, w))