CodeEff/ECCO huggingface dataset:
# Original solution
import heapq
import sys
def input(): return sys.stdin.readline()
from collections import defaultdict
class UnionFind():
    def __init__(self, num):
        self.par = [-1 for _ in range(num)]
    
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            x = self.par[x]
            return self.find(x)
    
    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            if self.par[rx] < self.par[ry]:
                self.par[ry] = rx
            if self.par[rx] > self.par[ry]:
                self.par[rx] = ry
            else:
                self.par[rx] -= 1
                self.par[ry] = rx
        return
def f(nb, nc):
    if nb != N-1:
        return (nb+1, nc)
    return 0
def g(nb, nc):
    if nc != N-1:
        return (nb, nc+1)
    return 0
def inpl(): return [int(i) for i in input().split()]

N, D = inpl()
A = inpl()
B = [(i*D + v, i) for i, v in enumerate(A, 1)]
C = [(-i*D + v, i) for i, v in enumerate(A, 1)]
B.sort()
C.sort()
Z = UnionFind(N+1)
Q = []
ctr = 0
ans = 0
H = defaultdict(lambda: False)
heapq.heappush(Q, (C[0][0] + B[0][0], (0, 0)))
H[(0, 0)] = True
H[0] = True
while ctr < N-1:
    v, (bi, ci) = heapq.heappop(Q)
    _, bj = B[bi]
    _, cj = C[ci]
    if not H[f(bi, ci)]:
        H[(bi+1, ci)] = True
        heapq.heappush(Q, (B[bi+1][0] + C[ci][0], (bi+1, ci)))
    if not H[g(bi, ci)]:
        H[(bi, ci+1)] = True
        heapq.heappush(Q, (B[bi][0] + C[ci+1][0], (bi, ci+1)))
    if bj <= cj:
        continue
    if Z.find(bj) == Z.find(cj):
        continue
    Z.union(bj, cj)
    ans += v
    ctr += 1
print(ans)

# Optimized solution
from operator import itemgetter
import itertools
def inpl(): return list(map(int, input().split()))
def cost(x, y):
    if x == y:
        return float('inf')
    return D * abs(x - y) + A[x] + A[y]
N, D = inpl()
A = inpl()
Right = [(v - i*D, i) for i, v in enumerate(A)]
Left = [(v + i*D, i) for i, v in enumerate(A)][::-1]
Right = list(map(itemgetter(1), itertools.accumulate(Right, min)))
Left = list(map(itemgetter(1), itertools.accumulate(Left, min)))[::-1]
ans = 0
hub = []
for i, (l, r) in enumerate(zip(Left, Right)) :
    if i == l == r:
        hub.append(i)
    else:
        ans += min(cost(i, r), cost(i, l))
print((ans + sum([cost(i, j) for i, j in zip(hub, hub[1:])])))
# Original solution
def judT(x, y):
  xR = x
  while T[xR][0] != xR:
    T[T[xR][0]][1] = T[xR][1] + 1
    xR = T[xR][0]
  yR = y
  while T[yR][0] != yR:
    T[T[yR][0]][1] = T[yR][1] + 1
    yR = T[yR][0]
  if xR != yR:
    if T[xR][1] < T[yR][1]:
      T[xR][0] = yR
      if T[yR][1] < T[xR][1] + 1:
        T[yR][1] = T[xR][1] + 1
    else:
      T[yR][0] = xR
      if T[xR][1] < T[yR][1] + 1:
        T[xR][1] = T[yR][1] + 1
  return xR != yR

N, D = list(map(int,input().split()))
A = list(map(int, input().split()))

rt = (N-1) * D + A[N-1]
Ll = [N-1]
k = N - 2
for i in range(N-2, 0, -1):
  t = (i - k) * D + A[i]
  if rt > t:
    Ll.append(i)
    k = i
    rt = A[i]
    
rt = (N-1) * D + A[0]
Lr = [0]
k = 0
for i in range(1, N-1):
  t = (k - i) * D + A[i]
  if rt > t:
    Lr.append(i)
    k = i
    rt = A[i]

Ch = [[0] * N for i in range(N)]
L = []
cnt = -1
for i in range(N-1):
  if i >= Ll[cnt]:
    cnt -= 1
  L.append((A[i] + A[Ll[cnt]] + (Ll[cnt] - i) * D, i, Ll[cnt]))
  Ch[i][Ll[cnt]] = 1

cnt = -1
for i in range(N-1, 0, -1):
  if i <= Lr[cnt]:
    cnt -= 1
  if Ch[Lr[cnt]][i] == 0:
  	L.append((A[i] + A[Lr[cnt]] + (i - Lr[cnt]) * D, Lr[cnt], i))

#print(L)
  
L.sort()

#print(L)

T = [[i, 0] for i in range(N)]
 
C = 0
A = 0
 
for i in L:
  if judT(i[1], i[2]):
    C += 1
    A += i[0]
    #print(i)
    if C == N-1:
      break
 
print(A)

# Optimized solution
def judT(x, y):
  xR = x
  xC = 0
  while T[xR] != xR:
    xC += 1
    xR = T[xR]
  yR = y
  yC = 0
  while T[yR] != yR:
    yC += 1
    yR = T[yR]
  if xR != yR:
    if xC < yC:
      T[xR] = yR
    else:
      T[yR] = xR
  return xR != yR

N, D = tuple(map(int,input().split()))
A = tuple(map(int, input().split()))

rt = A[N - 1]
Ll = [N - 1]
k = N - 1
for i in range(N - 2, 0, -1):
  t = A[i]  
  if rt > t - (k - i) * D :
    Ll.append(i)
    k = i
    rt = t

rt = A[0]
Lr = [0]
k = 0
for i in range(1, N - 1):
  t = A[i]
  if rt > t + (k - i) * D:
    Lr.append(i)
    k = i
    rt = t
Lr.append(N-1)

Ll = tuple(Ll)
Lr = tuple(Lr)

L = []
lC = -1
rC = 1
lCmax = -len(Ll) - 1
for i in range(N-1):
  if i >= Ll[lC]:
    lC -= 1
  for j in range(lC, lCmax, -1):
    t = Ll[j]
    if A[i] >= A[t]: 
      L.append((A[i] + A[t] + (t - i) * D, i, t))
      break
  k = i + 1
  if k > Lr[rC]:
    rC += 1
  for j in range(rC - 1, -1, -1):
    t = Lr[j]
    if A[k] > A[t]:
      L.append((A[k] + A[t] + (k - t) * D, t, k))
      break
L.sort()

T = [i for i in range(N)]
C = 0
A = 0
for i in L:
  if judT(i[1], i[2]):
    C += 1
    A += i[0]
    #print(i)
    if C == N-1:
      break
 
print(A)
# Original solution
s = input()[:-1]
for i in range(len(s)):
    x = s[:i]
    n = len(s[:i])
    if n%2==0 and x[:i//2]==x[i//2:]:
        ans = n
print(ans)

# Optimized solution
s = input()[:-1]

while s[:len(s)//2]*2 != s:
    s = s[:-1]

print((len(s)))
# Original solution
s = list(input().rstrip())
while len(s)>0:
  
  s.pop()
    
  n = len(s)//2
  
  if s[:n] == s[n:] and len(s) % 2 == 0:
    print((len(s)))
    break

# Optimized solution
s = input()[:-1]
while s[:len(s)//2] != s[len(s)//2:]:
  s = s[:-1]
print((len(s)))
# Original solution
import sys
stdin = sys.stdin

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

s = ns()

ans = 0
for n in range(len(s)//2-1,-1,-1):
    if s[:n] == s[n:2*n]:
        ans = n
        break
        
print((2*ans))

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

s = ns()
n = len(s)

ans = 0

for i in range(1,n//2):
    first = s[:i]
    second = s[i:2*i]
    
    if first == second:
        ans = 2*i
        
print(ans)
# Original solution
S = input().strip()
N = len(S)
for i in range(2,N,2):
    x = S[:-i]
    y = x[:(N-i)//2]
    z = x[(N-i)//2:]
    if y==z:
        print((N-i))
        break

# Optimized solution
S = input().strip()
N = len(S)
for i in range(N//2-1,0,-1):
    if S[:i]==S[i:2*i]:
        ans = i
        break
print((ans*2))
# Original solution
import re;print((len(re.match(r"(.+)\1",input()[:-1]).group())))

# Optimized solution
s=input()[:-1];print((max(i*2for i in range(99)if s[:i]==s[i:i*2])))
# Original solution
print((len(__import__("re").search(r"(.+)\1", input()[:-1]).group(0))))

# Optimized solution
def f(a):
    return a[:len(a) // 2] == a[len(a) // 2:]

a = input()[:-1]
while a:
    if f(a):
        print((len(a)))
        exit()
    else:
        a = a[:-1]
print((0))
# Original solution
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def is_even(S):
    if len(S) % 2 != 0:
        return False
    if S[: len(S) // 2] == S[len(S) // 2 :]:
        return True
    else:
        return False


def main():
    S = readline().strip()
    S = S[:-1]

    for w in range(len(S), 0, -1):
        for i in range(len(S) - w + 1):
            if is_even(S[i : i + w]):
                print(w)
                return

    return


if __name__ == '__main__':
    main()


# Optimized solution
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    S = readline().strip()
    N = len(S)

    for w in range(N // 2 - 1, 0, -1):
        ok = True
        for i in range(w):
            if S[i] != S[i + w]:
                ok = False
                break
        if ok:
            print((2 * w))
            return

    return


if __name__ == '__main__':
    main()
# Original solution
import sys
input = sys.stdin.readline
from collections import defaultdict

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

N,M = list(map(int,input().split()))
graph = defaultdict(list)
for _ in range(M):
    p,q,c = list(map(int,input().split()))
    graph[(p,0)].append((p,c))
    graph[(p,c)].append((p,0))
    graph[(q,0)].append((q,c))
    graph[(q,c)].append((q,0))
    graph[(p,c)].append((q,c))
    graph[(q,c)].append((p,c))

INF = 10 ** 9
dist = defaultdict(lambda: INF)

visited = set()
q = [(1,0)] # 0 が会社に属していない状態
dist[(1,0)] = 0
d = 0
while q:
    qq = []
    while q:
        v,c = q.pop()
        if c == 0:
            for v1,c1 in graph[(v,0)]:
                if dist[(v1,c1)] <= d + 1:
                    continue
                dist[(v1,c1)] = d + 1
                qq.append((v1,c1))
        else:
            for v1,c1 in graph[(v,c)]:
                if dist[(v1,c1)] <= d:
                    continue
                dist[(v1,c1)] = d
                q.append((v1,c1))
    d += 1
    q = qq

answer = dist[(N,0)]
if answer == INF:
    answer = -1
print(answer)

# Optimized solution
import sys
input = sys.stdin.readline
from collections import defaultdict

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

L = 32
mask = (1 << L) - 1
N,M = list(map(int,input().split()))
graph = defaultdict(list)
for _ in range(M):
    p,q,c = list(map(int,input().split()))
    p <<= L
    q <<= L
    graph[p].append(p+c)
    graph[p+c].append(p)
    graph[q].append(q+c)
    graph[q+c].append(q)
    graph[p+c].append(q+c)
    graph[q+c].append(p+c)

INF = 10 ** 9
dist = defaultdict(lambda: INF)

start = 1 << L
goal = N << L

q = [start] # 0 が会社に属していない状態
dist[start] = 0
d = 0
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)
# Original solution
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 = list(map(int, input().split()))
cost = [10**30 for _ in range(n)]
edges = defaultdict(list)
for _ in range(m):
	p, q, t = list(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)

# Optimized solution
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 = list(map(int, input().split()))
cost = [10**30 for _ in range(n)]
edges = defaultdict(list)
for _ in range(m):
	p, q, t = list(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)
# Original solution
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 = list(map(int, input().split()))
cost = [10**30 for _ in range(n)]
edges = defaultdict(list)
for _ in range(m):
	p, q, t = list(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)

# Optimized solution
import sys, heapq
from collections import defaultdict
def input():
	return sys.stdin.buffer.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 = list(map(int, input().split()))
cost = [10**30 for _ in range(n)]
edges = defaultdict(list)
for _ in range(m):
	p, q, t = list(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)
# Original solution
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 < dist[w]:
                dist[w] = cost
                que.appendleft((cost, 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 + 1 < gdist[w]:
                gdist[w] = cost + 1
                que.append((cost + 1, w, 1))

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


# Optimized solution
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))
# Original solution
from collections import defaultdict,deque
import sys
input=sys.stdin.readline
N,M=list(map(int,input().split()))
G=defaultdict(set)
Comps=[[] for i in range(N)]
for i in range(M):
  a,b,c=list(map(int,input().split()))
  G[(a-1,c-1)].add((b-1,c-1,0))
  G[(b-1,c-1)].add((a-1,c-1,0))
  Comps[a-1].append(c-1)
  Comps[b-1].append(c-1)
for i in range(N):
  for c in Comps[i]:
    G[(i,-1)].add((i,c,1))
    G[(i,c)].add((i,-1,0))
def BFS(x):
  visited=defaultdict(bool)
  stack=deque([(x,-1,0)])
  ans=0
  while stack:
    a,c,m=stack.popleft()
    if visited[(a,c)]:
      continue
    if a==N-1 and c==-1:
      return m
    for i in G[(a,c)]:
      if not visited[(i[0],i[1])]:
        if i[2]==0:
          stack.appendleft((i[0],i[1],m))
        else:
          stack.append((i[0],i[1],m+1))
    visited[(a,c)]=True
  return -1

print((BFS(0)))



      
    

# Optimized solution
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))
  exit()
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)))