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.

-----Sample Input-----
3 3
1 2 1
2 3 1
3 1 2

-----Sample Output-----
1

Use company 1's lines: 1 → 2 → 3. The fare is 1 yen.

Difficulty: competition

Starter code:

Solutions:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
from collections import deque
INF = 10**9

n, m = map(int, input().split())
pqc = []

seen = set()
for i in range(n):
    seen.add((i, 0))
for _ in range(m):
    p, q, c = map(int, input().split())
    p -= 1; q -= 1
    pqc.append((p, q, c))
    seen.add((p, c))
    seen.add((q, c))
comp = dict()
for i, node in enumerate(seen):
    comp[node] = i

edge = [[] for _ in range(len(comp))]
for key in comp.keys():
    v, c = key
    if c != 0:
        frm = comp[(v, c)]
        too = comp[(v, 0)]
        edge[frm].append((too, 0))
        edge[too].append((frm, 1))

for p, q, c in pqc:
    frm = comp[(p, c)]
    too = comp[(q, c)]
    edge[frm].append((too, 0))
    edge[too].append((frm, 0))

class BFS:
    def __init__(self, adj):
        self.adj = adj
        self.dist = [INF] * len(adj)
        self.q = deque()

    def calc(self, start):
        self.dist[start] = 0
        self.q.append((0, start))
        while len(self.q) != 0:
            prov_cost, src = self.q.popleft()
            if self.dist[src] < prov_cost:
                continue
            for dest, cost in self.adj[src]:
                if self.dist[dest] > self.dist[src] + cost:
                    self.dist[dest] = self.dist[src] + cost
                    if cost == 1:
                        self.q.append((self.dist[dest], dest))
                    else:
                        self.q.appendleft((self.dist[dest], dest))
        return self.dist

bfs = BFS(edge)
bfs.calc(comp[(0, 0)])
ans = bfs.dist[comp[(n-1, 0)]]
if ans == INF:
    print(-1)
else:
    print(ans)

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)

# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,m = list(map(int, readline().split()))

g = {}

for _ in range(m):
    p,q,c = list(map(int, readline().split()))
    pc = ((p-1)<<20)+c
    qc = ((q-1)<<20)+c
    pp = (p-1)<<20
    qq = (q-1)<<20
    
    if pc not in g: g[pc] = []
    if qc not in g: g[qc] = []
    if pp not in g: g[pp] = []
    if qq not in g: g[qq] = []
    
    g[pc].append(qc)
    g[pc].append(pp)

    g[qc].append(pc)
    g[qc].append(qq)

    g[pp].append(pc)
    g[qq].append(qc)

if 0 not in g: g[0] = []

from collections import deque
q = deque([(0,0)])
res = {0:0}

mask = (1<<20)-1
while q:
    vl,dv = q.popleft()
    if res[vl] < dv: continue
    if (vl>>20) == n-1:
        res[(n-1)<<20] = dv+1
        break
    for tl in g[vl]:
        ndv = dv + (vl&mask==0 or tl&mask==0)
        if tl not in res or res[tl] > ndv:
            res[tl] = ndv
            if vl&mask==0 or tl&mask==0:
                q.append((tl,ndv))
            else:
                q.appendleft((tl,ndv))

if (n-1)<<20 in res:
    print((res[(n-1)<<20]//2))
else:
    print((-1))






import sys
readline = sys.stdin.readline

from heapq import heappop as hpp, heappush as hp
inf = 10**9+7
def dijkstra(N, s, Edge):    
    dist = [inf] * N
    dist[s] = 0
    Q = [(0, s)]
    while Q:
        dn, vn = hpp(Q)
        if dn > dist[vn]:
            continue
        for df, vf in Edge[vn]:
            if dn + df < dist[vf]:
                dist[vf] = dn + df
                hp(Q, (dn + df,vf))
    return dist

def compress(L):
    L2 = list(set(L))
    L2.sort()
    C = {v : k for k, v in enumerate(L2)}
    return L2, C


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

Edge = []
VS = set(range(N))
geta = 20
Edge = [tuple(map(int, readline().split())) for _ in range(M)]
for a, b, c in Edge:
    a -= 1
    b -= 1
    VS |= {(c<<geta) | a, (c<<geta) | b}
   
_, Cv = compress(list(VS))

Vnum = len(Cv)

nEdge = [[] for _ in range(Vnum)]

for a, b, c in Edge:
    a -= 1
    b -= 1
    ca = Cv[(c<<geta) | a]
    cb = Cv[(c<<geta) | b]
    nEdge[ca].append((0, cb))
    nEdge[cb].append((0, ca))
    nEdge[a].append((1, ca))
    nEdge[ca].append((0, a))
    nEdge[b].append((1, cb))
    nEdge[cb].append((0, b))

dist = dijkstra(Vnum, 0, nEdge)
if dist[N-1] >= inf:
    dist[N-1] = -1
print(dist[N-1])  

import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return 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)

import sys
input = lambda: sys.stdin.readline().rstrip()
from collections import deque
N, M = map(int, input().split())
X = []
C = [set() for _ in range(N)]
for _ in range(M):
    p, q, c = [int(a) - 1 for a in input().split()]
    X.append((p, q, c))
    C[p].add(c)
    C[q].add(c)
for i, c in enumerate(C):
    C[i] = list(c)

I = [N]
D = [{} for _ in range(N)]
for i, c in enumerate(C):
    for j, a in enumerate(c):
        D[i][a] = I[-1] + j
    I.append(I[-1] + len(c))

T = I[-1]
E = [[] for _ in range(T)]
for p, q, c in X:
    E[D[p][c]].append((D[q][c], 0))
    E[D[q][c]].append((D[p][c], 0))
for i, c in enumerate(C):
    for j, a in enumerate(c):
        E[i].append((D[i][a], 1))
        E[D[i][a]].append((i, 1))

def BFS01(n, E, i0=0):
    Q = deque([i0])
    D = [-1] * n
    D[i0] = 0
    while Q:
        x = Q.popleft()
        for y, w in E[x]:
            if w:
                if D[y] == -1:
                    D[y] = D[x] + 1
                    Q.append(y)
            else:
                if D[y] == -1 or D[y] < D[x]:
                    D[y] = D[x]
                    Q.appendleft(y)
    return D

D = BFS01(T, E, 0)
print(D[N-1] // 2)

# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def bfs01(g, s):
    d = {}
    for v in g.keys():
        d[v] = sys.maxsize
    d[s] = 0

    if s not in d:
        return d
    q = deque()
    q.append((d[s], s))

    NM = 1 << 30
    while q:
        _, u = q.popleft()
        for v in g[u]:
            if v > NM:
                c = 0
            else:
                c = 1
            alt = c + d[u]
            if d[v] > alt:
                d[v] = alt
                if c == 0:
                    q.appendleft((d[v], v))
                else:
                    q.append((d[v], v))
    return d


@mt
def slv(N, M):

    g = defaultdict(list)
    NM = 30
    for _ in range(M):
        p, q, c = input().split()
        p = int(p)
        q = int(q)
        c = int(c)

        cp = (c << NM) + p
        cq = (c << NM) + q
        g[cp].append(cq)
        g[cq].append(cp)
        g[cp].append(p)
        g[cq].append(q)
        g[p].append((cp))
        g[q].append((cq))

    d = bfs01(g, 1)
    return -1 if N not in d or d[N] == sys.maxsize else d[N]


def main():
    N, M = read_int_n()

    print(slv(N, M))


def __starting_point():
    main()

__starting_point()

import sys,heapq
from collections import defaultdict,deque

input = sys.stdin.readline
n,m = map(int,input().split())
#+路線*chg : その路線ホーム
chg = 10**6

edge=defaultdict(set)
used =defaultdict(bool)
for i in range(m):
    p,q,c = map(int,input().split())
    edge[p].add(p+c*chg)
    edge[p+c*chg].add(p)
    edge[p+c*chg].add(q+c*chg)
    edge[q+c*chg].add(p+c*chg)
    edge[q].add(q+c*chg)
    edge[q+c*chg].add(q)
    used[p] = False
    used[q] = False
    used[p+c*chg] = False
    used[q+c*chg] = False

edgelist = deque()
edgelist.append((1,0))
res = float("inf")

while len(edgelist):
    x,cost = edgelist.pop()
    used[x] = True

    if x == n:
        res = cost
        break
    for e in edge[x]:
        if used[e]:
            continue
        #ホーム→改札
        if x <= 10**5 and chg <= e:
            edgelist.appendleft((e,cost+1))
        else:
            edgelist.append((e,cost))
        
if res == float("inf"):
    print(-1)
else:
    print(res)

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


class UnionFind:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

    def subsetall(self):
        a = []
        for i in range(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a

    def tall(self):
        d = collections.defaultdict(list)
        for i in range(len(self.table)):
            d[self.find(i)].append(i)
        return d

def main():
    M = 2**17
    n,m = LI()
    a = [LI() for _ in range(m)]
    e = collections.defaultdict(list)
    for p,q,c in a:
        pc = p+c*M
        qc = q+c*M
        pm = p-M
        qm = q-M
        e[pc].append(qc)
        e[qc].append(pc)
        e[pm].append(pc)
        e[qm].append(qc)
        e[pc].append(pm)
        e[qc].append(qm)

    def search():
        d = collections.defaultdict(lambda: inf)
        s = 1-M
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = set()
        while len(q):
            k, u = heapq.heappop(q)
            if u in v:
                continue
            v.add(u)
            if u < 0:
                for uv in e[u]:
                    if uv in v:
                        continue
                    vd = k + 1
                    if d[uv] > vd:
                        d[uv] = vd
                        heapq.heappush(q, (vd, uv))

            else:
                if u % M == n:
                    return k

                for uv in e[u]:
                    if uv in v:
                        continue
                    if d[uv] > k:
                        d[uv] = k
                        heapq.heappush(q, (k, uv))

        return -1

    return search()



print(main())


# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def bfs01(g, s):
    d = {}
    for v in g.keys():
        d[v] = sys.maxsize
    d[s] = 0

    if s not in d:
        return d
    q = deque()
    q.append((d[s], s))

    NM = 1 << 30
    while q:
        _, u = q.popleft()
        for v in g[u]:
            if v > NM:
                c = 0
            else:
                c = 1
            alt = c + d[u]
            if d[v] > alt:
                d[v] = alt
                if c == 0:
                    q.appendleft((d[v], v))
                else:
                    q.append((d[v], v))
    return d


@mt
def slv(N, M):

    g = defaultdict(list)
    NM = 30
    for _ in range(M):
        p, q, c = input().split()
        p = int(p)
        q = int(q)
        c = int(c)

        cp = (c << NM) + p
        cq = (c << NM) + q
        g[cp].append(cq)
        g[cq].append(cp)
        g[cp].append(p)
        g[cq].append(q)
        g[p].append((cp))
        g[q].append((cq))

    d = bfs01(g, 1)
    return -1 if N not in d or d[N] == sys.maxsize else d[N]


def main():
    N, M = read_int_n()

    print(slv(N, M))


def __starting_point():
    main()

__starting_point()

from collections import deque,defaultdict
import sys
input = sys.stdin.readline
N,M=map(int,input().split())
mod =10**7
table=defaultdict(set)
visit=defaultdict(int)
for i in range(M):
    a,b,c=map(int,input().split())
    table[a].add(a+c*mod)
    table[b].add(b+c*mod)
    table[a+c*mod].add(a)
    table[b+c*mod].add(b)
    table[a+c*mod].add(b+c*mod)
    table[b+c*mod].add(a+c*mod)
    visit[a]=0
    visit[b]=0
    visit[b+c*mod]=0
    visit[a+c*mod]=0

H=deque()
H.append((1,0))
visit[1]=1
ans=mod
while H:
    #print(H)
    x,cost=H.popleft()
    visit[x] = 1
    if x==N:
        ans=min(ans,cost)
        break
    for y in table[x]:
        if visit[y]==1:
            continue
        if x<=10**5 and mod<=y:
            H.append((y,cost+1))
        else:
            H.appendleft((y,cost))
if ans==mod:
    print(-1)
else:
    print(ans)

N, M = list(map(int, input().split()))
ES = []
D = {}

*parent, = list(range(M))
def root(x):
    if x == parent[x]:
        return x
    parent[x] = y = root(parent[x])
    return y
def unite(x, y):
    px = root(x); py = root(y)
    if px < py:
        parent[py] = px
    else:
        parent[px] = py

E = {}
for i in range(M):
    p, q, c = list(map(int, input().split())); p -= 1; q -= 1
    ES.append((p, q, c))
    if (p, c) in D:
        unite(D[p, c], i)
    D[p, c] = i
    E.setdefault(p, set()).add(c)
    if (q, c) in D:
        unite(D[q, c], i)
    D[q, c] = i
    E.setdefault(q, set()).add(c)
#P = [[] for i in range(M)]
P = {}
for i in range(M):
    j = root(i)
    p, q, c = ES[i]
    s = P.setdefault(j, set())
    s.add(p); s.add(q)

from collections import deque
que = deque([(0, 0, 0)])
INF = 10**18
dist = [INF]*N
dist[0] = 0
gdist = [INF]*M

while que:
    cost, v, t = que.popleft()
    if t:
        # edge
        if gdist[v] < cost or v not in P:
            continue
        for w in P[v]:
            if cost + 1 < dist[w]:
                dist[w] = cost + 1
                que.append((cost + 1, w, 0))
    else:
        # node
        if dist[v] < cost or v not in E:
            continue
        for c in E[v]:
            w = root(D[v, c])
            if cost < gdist[w]:
                gdist[w] = cost
                que.appendleft((cost, w, 1))

print((dist[N-1] if dist[N-1] < INF else -1))


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:
                        continue
                    dist[y[1]] = d
                    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 = list(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)


def main():
  from heapq import heappush,heappop,heapify
  inf=2**31-1
  n,m,*t=map(int,open(0).read().split())
  z=[]
  for a,b,c in zip(t[::3],t[1::3],t[2::3]):
    z.extend([a,b,a+n*c,b+n*c])
  z={i:v for v,i in enumerate(sorted(set(z)))}
  try:
    z[1]
  except:
    print(-1)
    return
  edge=[[]for _ in range(len(z))]
  d={}
  l=[]
  for a,b,c in zip(t[::3],t[1::3],t[2::3]):
    if b<a:a,b=b,a
    i,j,x,y=z[a],z[b],z[a+n*c],z[b+n*c]
    if b==n:
      l.append(y)
    edge[i].append((1,x))
    edge[j].append((1,y))
    edge[x].extend([(0,i),(0,y)])
    edge[y].extend([(0,j),(0,x)])
  used=[False]+[True]*~-len(z)
  d=[0]+[inf]*~-len(z)
  edgelist=edge[0]
  heapify(edgelist)
  while edgelist:
    m=heappop(edgelist)
    if not used[m[1]]:
      continue
    d[m[1]]=m[0]
    used[m[1]]=False
    for e in edge[m[1]]:
      if used[e[1]]:
        heappush(edgelist,(e[0]+m[0],e[1]))
  a=min([d[i]for i in l]or[inf])
  print([a,-1][a==inf])
def __starting_point():
  main()
__starting_point()

from collections import defaultdict
from collections import deque

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

chg = 10**6
G = defaultdict(set)
for _ in range(M):
    p, q, c = list(map(int, input().split()))
    # 無向グラフ
    G[p].add(p+chg*c)
    G[p+chg*c].add(p)
    G[q].add(q+chg*c)
    G[q+chg*c].add(q)
    G[p+chg*c].add(q+chg*c)
    G[q+chg*c].add(p+chg*c)


dist = defaultdict(lambda: 10**11)
dist[1] = 0

que = deque([1])

while que:
    ci = que.popleft()

    for ni in G[ci]:
        if dist[ni] == 10**11:
            if ci >= chg and ni >= chg:
                dist[ni] = dist[ci]
                que.appendleft(ni)
            else:
                dist[ni] = dist[ci]+1
                que.append(ni)


if dist[N] < 10**11:
    print((dist[N]//2))
else:
    print((-1))


def resolve():
    def Dijkstra(s, g):
        from collections import deque
        d = {s}
        queue = deque()
        for q in edge[s]:
            queue.append((1, q))
        while queue:
            dist, point = queue.popleft()
            if point in d:
                continue
            d.add(point)
            if point == g:
                return dist
            for nextp in edge[point]:
                if not nextp in d:
                    if not -1 in point or -1 in nextp:
                        queue.appendleft((dist, nextp))
                    else:
                        queue.append((dist + 1, nextp))
        return -1
    import sys
    input = sys.stdin.readline
    from collections import defaultdict
    n, m = list(map(int, input().split()))
    edge = defaultdict(set)
    for _ in range(m):
        p, q, c = list(map(int, input().split()))
        p, q = p - 1, q - 1
        edge[(p, c)].add((q, c))
        edge[(q, c)].add((p, c))
        edge[(p, c)].add((p, -1))
        edge[(q, c)].add((q, -1))
        edge[(p, -1)].add((p, c))
        edge[(q, -1)].add((q, c))
    print((Dijkstra((0, -1), (n - 1, -1))))


def __starting_point():
    resolve()

__starting_point()

# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,m,*pqc = list(map(int, read().split()))

g = {}
M = iter(pqc)

for p,q,c in zip(M,M,M):
    pc = ((p-1)<<20)+c
    qc = ((q-1)<<20)+c
    pp = (p-1)<<20
    qq = (q-1)<<20
    
    if pc not in g: g[pc] = []
    if qc not in g: g[qc] = []
    if pp not in g: g[pp] = []
    if qq not in g: g[qq] = []
    
    g[pc].append(qc)
    g[pc].append(pp)

    g[qc].append(pc)
    g[qc].append(qq)

    g[pp].append(pc)
    g[qq].append(qc)

if 0 not in g: g[0] = []

from collections import deque
q = deque([(0,0)])
res = {0:0}

mask = (1<<20)-1
while q:
    vl,dv = q.popleft()
    if res[vl] < dv: continue
    if (vl>>20) == n-1:
        res[(n-1)<<20] = dv+1
        break
    for tl in g[vl]:
        ndv = dv + (vl&mask==0 or tl&mask==0)
        if tl not in res or res[tl] > ndv:
            res[tl] = ndv
            if vl&mask==0 or tl&mask==0:
                q.append((tl,ndv))
            else:
                q.appendleft((tl,ndv))

if (n-1)<<20 in res:
    print((res[(n-1)<<20]//2))
else:
    print((-1))






import sys

int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

from collections import deque

def solve():
    dist = [inf] * len(to)
    q = deque()
    q.append((0, 0))
    dist[0] = 0
    while q:
        d, i = q.popleft()
        if d > dist[i]: continue
        if i < n:
            for j in to[i]:
                if dist[j] <= d + 1: continue
                dist[j] = d + 1
                q.append((d + 1, j))
        else:
            for j in to[i]:
                if j == n - 1:
                    print(dist[i])
                    return
                if dist[j] <= d: continue
                dist[j] = d
                q.appendleft((d, j))
    print(-1)

inf=10**9
n,m=MI()
to=[]
uctoi={}

for u in range(n):
    to.append([])
    uctoi[u,0]=u

for _ in range(m):
    u,v,c=MI()
    u,v=u-1,v-1
    if (u,c) not in uctoi:
        i=uctoi[u,c]=len(to)
        to.append([])
        to[i].append(u)
        to[u].append(i)
    else:i=uctoi[u,c]
    if (v,c) not in uctoi:
        j=uctoi[v,c]=len(to)
        to.append([])
        to[j].append(v)
        to[v].append(j)
    else:j=uctoi[v,c]
    to[i].append(j)
    to[j].append(i)
#print(to)
#print(fin)

solve()


import heapq

INF = 1000000000


def dijkstra(G, d, s):
    h = []
    d[s] = 0
    heapq.heappush(h, (0, s))

    while len(h) != 0:
        p = heapq.heappop(h)
        v = p[1]
        if d[v] < p[0]:
            continue
        for e in G[v]:
            if d[e[0]] > d[v] + e[1]:
                d[e[0]] = d[v] + e[1]
                heapq.heappush(h, (d[e[0]], e[0]))


def main():
    N, M = list(map(int, input().split()))
    p = [0] * M
    q = [0] * M
    c = [0] * M
    for i in range(M):
        p[i], q[i], c[i] = list(map(int, input().split()))
        p[i] -= 1
        q[i] -= 1
    plat = []
    for i in range(N):
        plat.append(dict())
    v_count = 0
    for i in range(M):
        p1 = plat[p[i]]
        if not c[i] in p1:
            p1[c[i]] = v_count
            v_count += 1
        p2 = plat[q[i]]
        if not c[i] in p2:
            p2[c[i]] = v_count
            v_count += 1
    for i in range(N):
        plat[i][-1] = v_count
        v_count += 1

    G = [[] for _ in range(v_count)]
    for i in range(M):
        p1 = plat[p[i]][c[i]]
        q1 = plat[q[i]][c[i]]
        G[p1].append((q1, 0))
        G[q1].append((p1, 0))
    for i in range(N):
        out = plat[i][-1]
        for v in list(plat[i].values()):
            if v == -1:
                continue
            G[v].append((out, 0))
            G[out].append((v, 1))

    start = plat[0][-1]
    goal = plat[N - 1][-1]

    d = [INF for _ in range(v_count)]

    dijkstra(G, d, start)

    if d[goal] == INF:
        print((-1))
    else:
        print((d[goal]))


def __starting_point():
    main()

__starting_point()

from collections import defaultdict, deque

N, M = list(map(int, input().split()))
D = {}
Edges = []


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # すべての頂点に対して親を検索する
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)


UF = UnionFind(M)
for i in range(M):
    p, q, c = list(map(int, input().split()))
    p, q = p-1, q-1
    Edges.append((p, q))

    if (p, c) in D:
        UF.union(D[p, c], i)
    D[p, c] = i

    if (q, c) in D:
        UF.union(D[q, c], i)
    D[q, c] = i

UF.all_find()

Firm_Node = defaultdict(set)
for i in range(M):
    p, q = Edges[i]
    Firm_Node[UF.par[i]].add(p)
    Firm_Node[UF.par[i]].add(q)

G = defaultdict(list)
for firm, node in list(Firm_Node.items()):
    for n in node:
        G[n].append(firm + N)
        G[firm + N].append(n)


def dijkstra(x):
    d = {x: 0, N-1: 10**9}
    visited = {x}

    # d, u
    queue = deque([(0, x)])

    while queue:
        u = queue.pop()[1]
        visited.add(u)

        for node in G[u]:
            d.setdefault(node, float('inf'))
            if (node not in visited) and d[node] > d[u] + 1:
                d[node] = d[u] + 1
                if d[N-1] < 10**9:
                    return d
                queue.appendleft([d[u]+1, node])
    return d


dist = dijkstra(0)
print((dist[N-1] // 2 if dist[N-1] < 2*M else -1))


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
from collections import deque, defaultdict
N, M = list(map(int, input().split()))
G = defaultdict(list)
for _ in range(M):
    p, q, c = list(map(int, input().split()))
    G[(p-1, c-1)].append((p-1, -1))
    G[(q-1, c-1)].append((q-1, -1))
    G[(p-1, -1)].append((p-1, c-1))
    G[(q-1, -1)].append((q-1, c-1))
    G[(p-1, c-1)].append((q-1, c-1))
    G[(q-1, c-1)].append((p-1, c-1))


dist = defaultdict(lambda :-1)
que = deque([(0, -1)])
dist[(0, -1)] = 0
while que:
    v = que.pop()
    d = dist[v]
    for nv in G[v]:
        if dist[nv]<0:
            if nv[1] == -1:
                dist[nv] = d+1
                que.appendleft(nv)
            else:
                dist[nv] = d
                que.append(nv)
print((dist[(N-1, -1)]))





import sys
from collections import defaultdict,deque

def main():
    input = sys.stdin.readline
    n,m = map(int,input().split())
    #+路線*chg : その路線ホーム
    chg = 10**6

    edge=defaultdict(set)
    used =defaultdict(bool)
    for i in range(m):
        p,q,c = map(int,input().split())
        edge[p].add(p+c*chg)
        edge[p+c*chg].add(p)
        edge[p+c*chg].add(q+c*chg)
        edge[q+c*chg].add(p+c*chg)
        edge[q].add(q+c*chg)
        edge[q+c*chg].add(q)
        used[p] = False
        used[q] = False
        used[p+c*chg] = False
        used[q+c*chg] = False

    edgelist = deque()
    edgelist.append((1,0))
    res = float("inf")
    while len(edgelist):
        x,cost = edgelist.pop()
        used[x] = True

        if x == n:
            res = cost
            break
        for e in edge[x]:
            if used[e]:
                continue
            #行先が改札
            if x <= 10**5 and chg <= e:
                edgelist.appendleft((e,cost+1))
            else:
                edgelist.append((e,cost))
            
    if res == float("inf"):
        print(-1)
    else:
        print(res)
def __starting_point():
    main()
__starting_point()

import sys
from collections import defaultdict,deque
input = sys.stdin.readline
n,m = map(int,input().split())
#+路線*chg : その路線ホーム
chg = 10**6

edge=defaultdict(set)
used =defaultdict(bool)
for i in range(m):
    p,q,c = map(int,input().split())
    edge[p].add(p+c*chg)
    edge[p+c*chg].add(p)
    edge[p+c*chg].add(q+c*chg)
    edge[q+c*chg].add(p+c*chg)
    edge[q].add(q+c*chg)
    edge[q+c*chg].add(q)
    used[p] = False
    used[q] = False
    used[p+c*chg] = False
    used[q+c*chg] = False

edgelist = deque()
edgelist.append((1,0))
res = float("inf")
while len(edgelist):
    x,cost = edgelist.pop()
    used[x] = True

    if x == n:
        res = cost
        break
    for e in edge[x]:
        if used[e]:
            continue
        #行先が改札
        if x <= 10**5 and chg <= e:
            edgelist.appendleft((e,cost+1))
        else:
            edgelist.append((e,cost))
        
if res == float("inf"):
    print(-1)
else:
    print(res)

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 collections import deque, defaultdict

n,m = li()
mod = 10**7

table = defaultdict(set)
visit = defaultdict(int)

for i in range(m):
    a,b,c = li()
    
    table[a].add(a + c*mod)
    table[b].add(b + c*mod)
    table[a + c*mod].add(a)
    table[b + c*mod].add(b)
    table[a + c*mod].add(b + c*mod)
    table[b + c*mod].add(a + c*mod)
    
    visit[a] = 0
    visit[b] = 0
    visit[b + c*mod] = 0
    visit[a + c*mod] = 0
    
que = deque()
que.append((1,0))

visit[1] = 1
ans = mod

while que:
    x, cost = que.popleft()
    visit[x] = 1
    
    if x == n:
        ans = min(ans, cost)
        break
    
    for y in table[x]:
        if visit[y] == 1:
            continue
        
        if x <= 10**5 and mod <= y:
            que.append((y, cost+1))
            
        else:
            que.appendleft((y, cost))
        
print((-1 if ans == mod else ans))


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

from collections import defaultdict,deque
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
N,M=list(map(int,input().split()))
if M==0:
  print((-1))
  return
G=defaultdict(set)
for i in range(M):
  a,b,c=list(map(int,input().split()))
  G[a+(c<<30)].add(b+(c<<30))
  G[b+(c<<30)].add(a+(c<<30))
  G[a].add(a+(c<<30))
  G[b].add(b+(c<<30))
  G[a+(c<<30)].add(a)
  G[b+(c<<30)].add(b)
def BFS(x):
  d={}
  for k in list(G.keys()):
    d[k]=float("inf")
  stack=deque([(x,0)])
  if x not in d:
    return -1
  while stack:
    s,m=stack.popleft()
    if s==N:
      return m
    if d[s]>m:
      d[s]=m
      if s>=(1<<30):
        for i in G[s]:
          if d[i]>10**30:
            stack.appendleft((i,m))
      else: 
        for i in G[s]:
          if d[i]>10**30:
            stack.append((i,m+1))
  return -1

print((BFS(1)))



      
    


import sys
input=sys.stdin.readline
from collections import defaultdict
from heapq import heappush, heappop,heappushpop,heapify
n,m = map(int, input().split())
link = defaultdict(list)
chg=10**8
for _ in range(m):
    p,q,c=map(int, input().split())
    link[p].append([p+chg*c,1])
    link[p+chg*c].append([p,1])

    link[q+chg*c].append([p+chg*c,0])
    link[p+chg*c].append([q+chg*c,0])

    link[q+chg*c].append([q,1])
    link[q].append([q+chg*c,1])

def dks(g,start):
    INF=float('inf')
    visited = set()
    hq = []
    heappush(hq, (0,start))
    while hq:
        shortest, i = heappop(hq)
        if i in visited:
            continue
        visited.add(i)
        for j, t in g[i]:
            if j in visited:
                continue
            if j==n:
                return (shortest+t)//2
            heappush(hq, (shortest + t, j))
    return -1
ans=dks(link,1)
print(ans)

import sys
input = sys.stdin.readline
from collections import defaultdict

"""
(駅、会社)を頂点にグラフを持つ。頂点数O(M)。
そのまま辺を貼ると辺が多くなりすぎる。
(駅、会社) -> (駅、無属性) -> (駅、会社)
"""

L = 32
mask = (1 << L) - 1
N,M = map(int,input().split())
graph = defaultdict(list)
for _ in range(M):
    p,q,c = 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)

def main():
    import sys
    from collections import deque
    input = sys.stdin.readline

    N, M = list(map(int, input().split()))
    adj = [[] for _ in range(N+1)]
    c2v = {}
    v = N+1
    for _ in range(M):
        p, q, c = list(map(int, input().split()))
        P = p*(10**7) + c
        Q = q*(10**7) + c
        if P not in c2v:
            c2v[P] = v
            adj[p].append((v, 1))
            adj.append([(p, 1)])
            v += 1
        if Q not in c2v:
            c2v[Q] = v
            adj[q].append((v, 1))
            adj.append([(q, 1)])
            v += 1
        adj[c2v[P]].append((c2v[Q], 0))
        adj[c2v[Q]].append((c2v[P], 0))

    que = deque()
    que.append(1)
    seen = [-1] * len(adj)
    seen[1] = 0
    while que:
        v = que.popleft()
        for u, cost in adj[v]:
            if seen[u] == -1:
                seen[u] = seen[v] + cost
                if cost:
                    que.append(u)
                else:
                    que.appendleft(u)
    print((seen[N] // 2))


def __starting_point():
    main()

__starting_point()

#!/usr/bin python3
# -*- coding: utf-8 -*-

# https://atcoder.jp/contests/arc061/tasks/arc061_c

########################################################
# 01BFS
########################################################

from collections import deque

n, m = list(map(int, input().split()))
ab = set([])
ps = set([i<<20 for i in range(1, n+1)])

for _ in range(m):
    a, b, c = list(map(int, input().split()))
    a <<= 20
    b <<= 20
    ps.add(a+c)
    ps.add(b+c)
    ab.add((a, b, c))


psr = {ps:i for i, ps in enumerate(ps)}
psc = len(ps)
gmap = [[] for _ in range(psc)]
for a, b, c in ab:
    a0 = psr[a]
    b0 = psr[b]
    a1 = psr[a+c]
    b1 = psr[b+c]
    gmap[a0].append((a1, 1))
    gmap[b0].append((b1, 1))
    gmap[a1].append((a0, 0))
    gmap[b1].append((b0, 0))
    gmap[a1].append((b1, 0))
    gmap[b1].append((a1, 0))

INF = float('inf')
dist = [INF] * psc

def zero_one_bfs(sp, gp):
    next_q = deque([])
    next_q.append(sp)
    dist[sp] = 0
    while next_q:
        cp = next_q.popleft()
        cd = dist[cp]
        if cp == gp: return cd
        for np, pay in gmap[cp]:
            if dist[np] <= cd+pay: continue
            dist[np] = cd + pay
            if pay == 1:
                next_q.append(np)
            else:
                next_q.appendleft(np)
    return dist[gp]

ret = zero_one_bfs(psr[1<<20], psr[n<<20])
print((-1 if ret == INF else ret))


N, M = list(map(int, input().split()))
ES = []
D = [{} for i in range(N)]

*parent, = list(range(M))
def root(x):
    if x == parent[x]:
        return x
    parent[x] = y = root(parent[x])
    return y
def unite(x, y):
    px = root(x); py = root(y)
    if px < py:
        parent[py] = px
    else:
        parent[px] = py

E = {}
for i in range(M):
    p, q, c = list(map(int, input().split())); p -= 1; q -= 1
    ES.append((p, q, c))
    if c in D[p]:
        unite(D[p][c], i)
    else:
        D[p][c] = i
    E.setdefault(p, set()).add(c)
    if c in D[q]:
        unite(D[q][c], i)
    else:
        D[q][c] = i
    E.setdefault(q, set()).add(c)
P = {}
for i in range(M):
    p, q, c = ES[i]
    s = P.setdefault(root(i), set())
    s.add(p); s.add(q)

from collections import deque
que = deque([(0, 0, 0)])
INF = 10**18
dist = [INF]*N
dist[0] = 0
gdist = [INF]*M

while que:
    cost, v, t = que.popleft()
    if t:
        # edge
        if gdist[v] < cost or v not in P:
            continue
        for w in P[v]:
            if cost + 1 < dist[w]:
                dist[w] = cost + 1
                que.append((cost + 1, w, 0))
    else:
        # node
        if dist[v] < cost or v not in E:
            continue
        for w in list(D[v].values()):
            w = root(w)
            if cost < gdist[w]:
                gdist[w] = cost
                que.appendleft((cost, w, 1))

print((dist[N-1] if dist[N-1] < INF else -1))


from collections import *
import sys 
sys.setrecursionlimit(10 ** 9)

def solve():
    def dfs(u, f):
        G[u].append(f)
        G1[f].append(u)
        for v in g[u]:
            if v not in used:
                used.add(v)
                dfs(v, f)

    n, m = list(map(int, input().split()))
    edges = []
    for  _ in range(m):
        edges.append(list(map(int, input().split())))
    edges.sort(key = lambda item: item[2])
    G = defaultdict(list)#记录每个点可能在哪个分组里面
    G1 = defaultdict(list) #记录每个分组里面的点
    en = 0
    cnt = 0
    while en < len(edges):
        st = en 
        g = defaultdict(list)
        used = set()
        while en < len(edges) and edges[en][2] == edges[st][2]:
            x, y = edges[en][0], edges[en][1]
            g[x].append(y)
            g[y].append(x)
            en += 1
        for k in g:
            if k not in used:
                used.add(k)
                dfs(k, cnt)
                cnt += 1
    
    usedG = set()
    usedP = set()
    deq = deque()
    deq.append(1)
    usedP.add(1)
    step = 0
    while deq:
        siz = len(deq)
        for _ in range(siz):
            f = deq.popleft()
            if f == n:
                print(step)
                return 
            for g in G[f]:
                if g not in usedG:
                    usedG.add(g)
                    for p in G1[g]:
                        if p not in usedP:
                            usedP.add(p)
                            deq.append(p)
        step += 1
    
    print((-1))

solve()



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 = list(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)


def main():
  N,M=map(int,input().split())

  if M == 0:
    print(-1)
    return

  INF = 10**6
  pqc = [tuple(map(lambda x:int(x)-1,input().split())) for _ in range(M)]

  to1d={v:{} for v in range(N)}
  count=2
  for p,q,c in pqc:
    if not to1d[p].get(c):
      to1d[p][c] = count
      count += 1
    if not to1d[q].get(c):
      to1d[q][c] = count
      count += 1

  G = [{} for _ in range(N+count)]
  for p,q,c in pqc:
    v1,v2 = to1d[p][c],to1d[q][c]
    G[v1][v2] = G[v2][v1] = 0

  for i in range(N):
    if len(to1d[i])<=1: continue
    for c in to1d[i].keys():
      v = to1d[i][c]
      G[v][count] = 1
      G[count][v] = 0
    count += 1

  def dijkstra(start = 0, goal = 1):
      from heapq import heappop, heappush
      NN = len(G)
      d = [INF]*NN
      d[start] = 0
      que = []
      heappush(que, start)
      while que:
          p = divmod(heappop(que),NN)
          v = p[1]
          if d[v] < p[0]: continue
          for u in G[v].keys():
              if d[u] > d[v] + G[v][u]:
                  d[u] = d[v] + G[v][u]
                  heappush(que, d[u]*NN+u)
          if v == goal: return d[goal]
      return d[goal]

  for c in to1d[0].keys():
    v = to1d[0][c]
    G[0][v] = 1
  for c in to1d[N-1].keys():
    v = to1d[N-1][c]
    G[v][1] = 0

  ans = dijkstra(0,1)
  print(ans if ans < INF else -1)
  
def __starting_point():
  main()
__starting_point()

import sys
input = sys.stdin.readline
from collections import defaultdict

"""
(駅、会社)を頂点にグラフを持つ。頂点数O(M)。
そのまま辺を貼ると辺が多くなりすぎる。
(駅、会社) -> (駅、無属性) -> (駅、会社)
"""

L = 32
mask = (1 << L) - 1
N,M = map(int,input().split())
graph = defaultdict(list)
for _ in range(M):
    p,q,c = 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
while q:
    qq = []
    while q:
        x = q.pop()
        if x & mask == 0:
            for y in graph[x]:
                if dist[y] <= d + 1:
                    continue
                dist[y] = d + 1
                qq.append(y)
        else:
            for y in graph[x]:
                if dist[y] <= d:
                    continue
                dist[y] = d
                q.append(y)
    d += 1
    q = qq

answer = dist[goal]
if answer == INF:
    answer = -1
print(answer)

# https://juppy.hatenablog.com/entry/2019/04/10/ARC061_-_E_%E3%81%99%E3%81%AC%E3%81%91%E5%90%9B%E3%81%AE%E5%9C%B0%E4%B8%8B%E9%89%84%E6%97%85%E8%A1%8C_-_Python_%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0_Atcoder
# 参考にさせていただきました。

from collections import deque, defaultdict

chg = 10**6
n, m = map(int, input().split())
edges = defaultdict(set)
# m=0のためにdefaultdictにしておくべき
visited = defaultdict(set)
for i in range(m):
    p, q, c = map(int, input().split())
    edges[p+c*chg].add(q+c*chg)
    edges[q+c*chg].add(p+c*chg)
    edges[p].add(p+c*chg)
    edges[q].add(q+c*chg)
    edges[p+c*chg].add(p)
    edges[q+c*chg].add(q)
    visited[p] = False
    visited[q] = False
    visited[p+c*chg] = False
    visited[q+c*chg] = False

ans = float("inf")
que = deque()
# now, dist
que.append((1, 0))
# 今求めるのはendの距離だけなので、dist配列はいらない
# さらに、距離は0/1なのでheapで辺を管理する必要もなく、0なら最短確定なので先に、1ならその時点での最長なので後ろにすれば良い
while que:
    now, dist = que.popleft()
    if visited[now]:
        continue
    visited[now] = True
    if now == n:
        ans = dist
        break
    for to in edges[now]:
        # 駅→ホーム
        if now < chg and to > chg:
            que.append((to, dist+1))
        else:
            que.appendleft((to, dist))
if ans == float("inf"):
    print(-1)
else:
    print(ans)

import sys
input = lambda: sys.stdin.readline().rstrip()
from collections import deque
N, M = map(int, input().split())
X = []
C = [set() for _ in range(N)]
for _ in range(M):
    p, q, c = [int(a) - 1 for a in input().split()]
    X.append((p, q, c))
    C[p].add(c)
    C[q].add(c)
for i, c in enumerate(C):
    C[i] = list(c)

I = [N]
D = [{} for _ in range(N)]
for i, c in enumerate(C):
    for j, a in enumerate(c):
        D[i][a] = I[-1] + j
    I.append(I[-1] + len(c))

T = I[-1]
E = [[] for _ in range(T)]
for p, q, c in X:
    E[D[p][c]].append((D[q][c], 0))
    E[D[q][c]].append((D[p][c], 0))
for i, c in enumerate(C):
    for j, a in enumerate(c):
        E[i].append((D[i][a], 1))
        E[D[i][a]].append((i, 1))

def BFS01(n, E, i0=0):
    Q = deque([i0])
    D = [-1] * n
    D[i0] = 0
    while Q:
        x = Q.popleft()
        for y, w in E[x]:
            if D[y] == -1:
                if w:
                    D[y] = D[x] + 1
                    Q.append(y)
                else:
                    D[y] = D[x]
                    Q.appendleft(y)
    return D

D = BFS01(T, E, 0)
print(D[N-1] // 2)

import sys, heapq
from collections import defaultdict
def input():
	return sys.stdin.readline()[:-1]

class DijkstraList():
	#隣接リスト版
	#同一頂点の複数回探索を防ぐため訪問した頂点数を変数cntで持つ
	def __init__(self, adj, start):
		self.list = adj
		self.start = start
		self.size = len(adj)

	def solve(self):
		#self.dist = [float("inf") for _ in range(self.size)]
		self.dist = defaultdict(lambda :10**30)
		self.dist[self.start] = 0
		#self.prev = [-1 for _ in range(self.size)]
		self.q = []
		self.cnt = 0

		heapq.heappush(self.q, (0, self.start))

		while self.q and self.cnt < self.size:
			u_dist, u = heapq.heappop(self.q)
			if self.dist[u] < u_dist:
				continue
			for v, w in self.list[u]:
				if self.dist[v] > u_dist + w:
					self.dist[v] = u_dist + w
					#self.prev[v] = u
					heapq.heappush(self.q, (self.dist[v], v))
			self.cnt += 1
		return

	def distance(self, goal):
		return self.dist[goal]

n, m = map(int, input().split())
cost = [10**30 for _ in range(n)]
edges = defaultdict(list)
for _ in range(m):
	p, q, t = map(int, input().split())
	edges[p-1 + t * n].append((q-1 + t * n, 0))
	edges[q-1 + t * n].append((p-1 + t * n, 0))
	if len(edges[p-1 + t * n]) == 1:
		edges[p-1 + t * n].append((p-1 + 0 * n, 0))
		edges[p-1 + 0 * n].append((p-1 + t * n, 1))
	if len(edges[q-1 + t * n]) == 1:
		edges[q-1 + t * n].append((q-1 + 0 * n, 0))
		edges[q-1 + 0 * n].append((q-1 + t * n, 1))

d = DijkstraList(edges, 0)
d.solve()
res = d.distance(n-1)
if res > 10**20:
	print(-1)
else:
	print(res)

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)

import sys
input = sys.stdin.readline
from collections import defaultdict, deque

n, m = map(int, input().split())
G = defaultdict(set)
U = 10**6
seen = set()
for _ in range(m):
  p, q, c = map(int, input().split())
  G[p+U*c].add((q+U*c, 0))
  G[q+U*c].add((p+U*c, 0))
  G[p+U*c].add((p-U, 0))
  G[q+U*c].add((q-U, 0))
  G[p-U].add((p+U*c, 1))
  G[q-U].add((q+U*c, 1))
que = deque()
que.append((1-U, 0))
while que:
  v, cnt = que.popleft()
  if v in seen:
    continue
  if v == n-U:
    print(cnt)
    return
  seen.add(v)
  for nv, cost in G[v]:
    if cost == 0:
      que.appendleft((nv, cnt+cost))
    else:
      que.append((nv, cnt+cost))
print(-1)

import sys
input=sys.stdin.readline
from collections import defaultdict,deque
n,m=map(int,input().split())
route=10**6
Edges=defaultdict(set)
Visited=defaultdict(bool)
for _ in range(m):
    p,q,c=map(int,input().split())
    Edges[p].add(p+c*route)
    Edges[p+c*route].add(p)
    Edges[p+c*route].add(q+c*route)
    Edges[q+c*route].add(p+c*route)
    Edges[q].add(q+c*route)
    Edges[q+c*route].add(q)
q=deque()
q.append((1,0))
cost=-1
while q:
    fr,c=q.popleft()
    Visited[fr]=True
    if fr==n:
        cost=c
        break
    for to in Edges[fr]:
        if Visited[to]:
            continue
        if fr<=10**5 and to>route:
            q.append((to,c+1))
        else:
            q.appendleft((to,c))
print(cost)

import sys, heapq
from collections import defaultdict
def input():
	return sys.stdin.readline()[:-1]

class DijkstraList():
	#隣接リスト版
	#同一頂点の複数回探索を防ぐため訪問した頂点数を変数cntで持つ
	def __init__(self, adj, start):
		self.list = adj
		self.start = start
		self.size = len(adj)

	def solve(self):
		#self.dist = [float("inf") for _ in range(self.size)]
		self.dist = defaultdict(lambda :10**30)
		self.dist[self.start] = 0
		#self.prev = [-1 for _ in range(self.size)]
		self.q = []
		self.cnt = 0

		heapq.heappush(self.q, (0, self.start))

		while self.q and self.cnt < self.size:
			u_dist, u = heapq.heappop(self.q)
			if self.dist[u] < u_dist:
				continue
			for v, w in self.list[u]:
				if self.dist[v] > u_dist + w:
					self.dist[v] = u_dist + w
					#self.prev[v] = u
					heapq.heappush(self.q, (self.dist[v], v))
			self.cnt += 1
		return

	def distance(self, goal):
		return self.dist[goal]

n, m = map(int, input().split())
cost = [10**30 for _ in range(n)]
edges = defaultdict(list)
for _ in range(m):
	p, q, t = map(int, input().split())
	edges[p-1 + t * n].append((q-1 + t * n, 0))
	edges[q-1 + t * n].append((p-1 + t * n, 0))
	if len(edges[p-1 + t * n]) == 1:
		edges[p-1 + t * n].append((p-1 + 0 * n, 0))
		edges[p-1 + 0 * n].append((p-1 + t * n, 1))
	if len(edges[q-1 + t * n]) == 1:
		edges[q-1 + t * n].append((q-1 + 0 * n, 0))
		edges[q-1 + 0 * n].append((q-1 + t * n, 1))

d = DijkstraList(edges, 0)
d.solve()
res = d.distance(n-1)
if res > 10**20:
	print(-1)
else:
	print(res)

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


class UnionFind:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

    def subsetall(self):
        a = []
        for i in range(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a

    def tall(self):
        d = collections.defaultdict(list)
        for i in range(len(self.table)):
            d[self.find(i)].append(i)
        return d

def main():
    M = 2**17
    n,m = LI()
    a = [LI() for _ in range(m)]
    e = collections.defaultdict(list)
    for p,q,c in a:
        pc = p+c*M
        qc = q+c*M
        pm = p-M
        qm = q-M
        e[pc].append(qc)
        e[qc].append(pc)
        e[pm].append(pc)
        e[qm].append(qc)
        e[pc].append(pm)
        e[qc].append(qm)

    def search():
        d = collections.defaultdict(lambda: inf)
        s = 1-M
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = set()
        while len(q):
            k, u = heapq.heappop(q)
            if u in v:
                continue
            v.add(u)
            if u < 0:
                for uv in e[u]:
                    if uv in v:
                        continue
                    vd = k + 1
                    if d[uv] > vd:
                        d[uv] = vd
                        heapq.heappush(q, (vd, uv))

            else:
                if u % M == n:
                    return k

                for uv in e[u]:
                    if uv in v:
                        continue
                    if d[uv] > k:
                        d[uv] = k
                        heapq.heappush(q, (k, uv))

        return -1

    return search()



print(main())


import sys
input = sys.stdin.readline
from collections import defaultdict

"""
(駅、会社)を頂点にグラフを持つ。頂点数O(M)。
そのまま辺を貼ると辺が多くなりすぎる。
(駅、会社) -> (駅、無属性) -> (駅、会社)
"""

L = 32
mask = (1 << L) - 1
N,M = map(int,input().split())
graph = defaultdict(list)
for _ in range(M):
    p,q,c = 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)

from sys import setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import bisect
from heapq import *

def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

N, M = reads()
edges = [[] for _ in range(N)]
edgesc = defaultdict(lambda: [])
for _ in range(M):
  p, q, c = reads()
  p, q = p-1, q-1
  edges[p].append((q, c))
  edges[q].append((p, c))
  edgesc[p, c].append(q)
  edgesc[q, c].append(p)

INF = 1 << 30
def dijkstra(edges, s):
  result = defaultdict(lambda: INF)
  result[s, -1] = 0
  que = deque([(0, s, -1)])
  while len(que) > 0:
    (d, u, c) = que.popleft()
    if result[u, c] < d:
      continue
    if c < 0:
      for (t, c2) in edges[u]:
        if d + 1 < result[t, c2]:
          result[t, c2] = d + 1
          que.append((d + 1, t, c2))
    else:
      for t in edgesc[u, c]:
        if d < result[t, c]:
          result[t, c] = d
          que.appendleft((d, t, c))
      if d < result[u, -1]:
        result[u, -1] = d
        que.appendleft((d, u, -1))
  return result

dist = dijkstra(edges, 0)
try:
  print(min(d for (u, _), d in dist.items() if u == N-1))
except ValueError:
  print(-1)