AtCoder Regular Contest 061 - Snuke's Subway Trip

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.

Source: atcoder | Difficulty: HARD


Solutions:
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)
solve()


import sys
from collections import defaultdict, deque

def main():
	input = sys.stdin.readline
	(n, m) = map(int, input().split())
	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()


from collections import deque
import sys
input = sys.stdin.buffer.readline

def bfs():
	dp[sup_v][0] = 1
	q1 = deque([sup_v])
	q2 = deque([0])
	while q1:
		v1 = q1.popleft()
		v2 = q2.popleft()
		for tmp in graph[v1 * OFFSET + v2]:
			(nxt_v1, nxt_v2) = divmod(tmp, OFFSET)
			if nxt_v1 == -1:
				cost = 1
			else:
				cost = 0
			if nxt_v1 not in dp:
				dp[nxt_v1] = {}
			if nxt_v2 not in dp[nxt_v1]:
				dp[nxt_v1][nxt_v2] = dp[v1][v2] + cost
				if cost == 0:
					q1.appendleft(nxt_v1)
					q2.appendleft(nxt_v2)
				else:
					q1.append(nxt_v1)
					q2.append(nxt_v2)
			elif dp[v1][v2] + cost < dp[nxt_v1][nxt_v2]:
				dp[nxt_v1][nxt_v2] = dp[v1][v2] + cost
				if cost == 0:
					q1.appendleft(nxt_v1)
					q2.appendleft(nxt_v2)
				else:
					q1.append(nxt_v1)
					q2.append(nxt_v2)
(n, m) = map(int, input().split())
INF = 10 ** 18
OFFSET = 10 ** 6
sup_v = -1
graph = {sup_v * OFFSET: []}
for _ in range(m):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	if c * OFFSET + a not in graph:
		graph[c * OFFSET + a] = []
		graph[c * OFFSET + a].append(sup_v * OFFSET + a)
	if c * OFFSET + b not in graph:
		graph[c * OFFSET + b] = []
		graph[c * OFFSET + b].append(sup_v * OFFSET + b)
	if sup_v * OFFSET + a not in graph:
		graph[sup_v * OFFSET + a] = []
	if sup_v * OFFSET + b not in graph:
		graph[sup_v * OFFSET + b] = []
	graph[c * OFFSET + a].append(c * OFFSET + b)
	graph[c * OFFSET + b].append(c * OFFSET + a)
	graph[sup_v * OFFSET + a].append(c * OFFSET + b)
	graph[sup_v * OFFSET + b].append(c * OFFSET + a)
dp = {sup_v: {}}
bfs()
ans = INF
for i in dp:
	for j in dp[i]:
		if j == n - 1:
			ans = min(dp[i][j], ans)
if ans == INF:
	print(-1)
else:
	print(ans)


import sys
input = sys.stdin.readline
from collections import defaultdict
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]
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)


class UnionFindVerSize:

	def __init__(self, init):
		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):
		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 = 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]
		return self._size[self.find_root(x, 0)]

	def is_same_group(self, x, y):
		x = self._dict[x]
		y = self._dict[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 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) = map(int, input().split())
	p = [0] * M
	q = [0] * M
	c = [0] * M
	for i in range(M):
		(p[i], q[i], c[i]) = 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 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])
main()


from collections import deque
(N, M) = map(int, input().split())
F_C_of_S = [{} for i in range(N)]
C_of_S = {}
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
pqcs = []
for i in range(M):
	(p, q, c) = map(int, input().split())
	p -= 1
	q -= 1
	pqcs += [(p, q, c)]
	if not c in F_C_of_S[p]:
		F_C_of_S[p][c] = i
	else:
		unite(F_C_of_S[p][c], i)
	C_of_S.setdefault(p, set()).add(c)
	if not c in F_C_of_S[q]:
		F_C_of_S[q][c] = i
	else:
		unite(F_C_of_S[q][c], i)
	C_of_S.setdefault(q, set()).add(c)
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)])
dist = [float('inf')] * N
dist[0] = 0
gdist = [float('inf')] * M
while Q:
	(cost, v, flag) = Q.popleft()
	if not flag:
		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:
		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)


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


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)


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

def main():
	(n, m) = map(int, input().split())
	edges = [[] for _ in range(n)]
	cedges = defaultdict(lambda : [])
	for _ in range(m):
		(p, q, c) = map(int, input().split())
		edges[p - 1].append((q - 1, c))
		edges[q - 1].append((p - 1, c))
		cedges[p - 1, c].append(q - 1)
		cedges[q - 1, c].append(p - 1)
	ans = defaultdict(lambda : float('inf'))
	ans[0, -1] = 0
	que = deque([(0, 0, -1)])
	while len(que) > 0:
		(d, u, c) = que.popleft()
		if ans[u, c] < d:
			continue
		if c < 0:
			for (t, c2) in edges[u]:
				if d + 1 < ans[t, c2]:
					ans[t, c2] = d + 1
					que.append((d + 1, t, c2))
		else:
			for t in cedges[u, c]:
				if d < ans[t, c]:
					ans[t, c] = d
					que.appendleft((d, t, c))
			if d < ans[u, -1]:
				ans[u, -1] = d
				que.appendleft((d, u, -1))
	try:
		print(min((d for ((u, _), d) in ans.items() if u == n - 1)))
	except ValueError:
		print(-1)
main()


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


from collections import deque, defaultdict
chg = 10 ** 6
(n, m) = map(int, input().split())
edges = defaultdict(set)
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()
que.append((1, 0))
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
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)


(N, M) = map(int, input().split())
ES = []
D = {}
(*parent,) = 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) = 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):
	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:
		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:
		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)


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
from collections import deque, defaultdict
(N, M) = map(int, input().split())
G = defaultdict(list)
for _ in range(M):
	(p, q, c) = 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])


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)
		exit()
	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])
main()


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)


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


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 dijkstra_heap(s, edge, mask):
	dist = defaultdict(lambda : float('inf'))
	q = [s]
	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)
	L = 32
	Mask = (1 << L) - 1
	for i in range(M):
		(p, q, c) = 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)
	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)


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
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque
(N, M) = map(int, readline().split())
if M == 0:
	print(-1)
	exit()
m = map(int, read().split())
(P, Q, C) = zip(*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 = 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)
			elif 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)


def main():
	import sys
	from collections import deque
	input = sys.stdin.readline
	(N, M) = map(int, input().split())
	adj = [[] for _ in range(N + 1)]
	c2v = {}
	v = N + 1
	for _ in range(M):
		(p, q, c) = 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)
main()


import sys
from collections import deque, defaultdict

def bfs01(s, t, links):
	q = deque([(0, s, -1)])
	visited = set()
	while q:
		(d, v, e) = q.popleft()
		if v == t:
			return d
		if (v, e) in visited:
			continue
		visited.add((v, e))
		if e == 0:
			for (c, us) in links[v].items():
				for u in us:
					if (u, c) in visited:
						continue
					q.append((d + 1, u, c))
		else:
			for u in links[v][e]:
				if (u, e) in visited:
					continue
				q.appendleft((d, u, e))
			if (v, 0) not in visited:
				q.appendleft((d, v, 0))
	return -1
readline = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
(n, m) = map(int, readline().split())
links = [defaultdict(set) for _ in range(n)]
pqc = list(map(int, read().split()))
for (p, q, c) in zip(pqc[0::3], pqc[1::3], pqc[2::3]):
	p -= 1
	q -= 1
	links[p][c].add(q)
	links[q][c].add(p)
print(bfs01(0, n - 1, links))


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 main():
	(N, M) = map(int, input().split())
	if M == 0:
		print(-1)
		exit()
	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)
main()


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)


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


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)


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

def input():
	return sys.stdin.readline()[:-1]

class DijkstraList:

	def __init__(self, adj, start):
		self.list = adj
		self.start = start
		self.size = len(adj)

	def solve(self):
		self.dist = defaultdict(lambda : 10 ** 30)
		self.dist[self.start] = 0
		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
					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)


def main():
	import sys
	read = sys.stdin.buffer.read
	readline = sys.stdin.buffer.readline
	readlines = sys.stdin.buffer.readlines
	sys.setrecursionlimit(10 ** 7)
	from collections import deque, defaultdict
	(n, m) = map(int, readline().split())
	graph = [defaultdict(set) for _ in range(n + 1)]
	for _ in range(m):
		(p, q, c) = map(int, readline().split())
		graph[p][c].add(q)
		graph[q][c].add(p)
	q = deque([(1, 0, -1)])
	vis = set()
	while q:
		(now, v, c) = q.popleft()
		if now == n:
			print(v)
			exit()
		if (now, c) in vis:
			continue
		vis.add((now, c))
		if c == 0:
			for cc in graph[now]:
				for next in graph[now][cc]:
					if (next, cc) not in vis:
						q.append((next, v + 1, cc))
		else:
			for next in graph[now][c]:
				if (next, c) not in vis:
					q.appendleft((next, v, c))
			if (now, 0) not in vis:
				q.appendleft((now, v, 0))
	print(-1)
main()


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


from heapq import heappush, heappop, heapify
import sys
input = sys.stdin.buffer.readline
(N, M) = map(int, input().split())
C = set()
edges = [[] for _ in range(N)]
for _ in range(M):
	(fr, to, c) = map(int, input().split())
	fr -= 1
	to -= 1
	edges[fr].append((to, c))
	edges[to].append((fr, c))
	C.add(c)
minDist = [10 ** 18] * (N + 1)
minDistList = [set() for _ in range(N)]
minDistList[0] = C
que = [(1, 0, 0)]
while que:
	(dist, f, now) = heappop(que)
	for (to, c) in edges[now]:
		d = dist
		if not c in minDistList[now]:
			d += 1
		if minDist[to] > d:
			minDist[to] = d
			minDistList[to] = set()
			heappush(que, (d, f + 1, to))
		if minDist[to] == d:
			minDistList[to].add(c)
for _ in range(2):
	que = [(minDist[i], 0, i) for i in range(N)]
	heapify(que)
	while que:
		(dist, f, now) = heappop(que)
		for (to, c) in edges[now]:
			d = dist
			if not c in minDistList[now]:
				d += 1
			if minDist[to] > d:
				minDist[to] = d
				minDistList[to] = set()
				heappush(que, (d, f + 1, to))
			if minDist[to] == d:
				minDistList[to].add(c)
ans = minDist[N - 1]
print(ans if ans < 10 ** 18 else -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)


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