Consider an undirected graph containing $N$ nodes and $\mbox{M}$ edges. Each edge $\textit{M}_i$ has an integer cost, $C_i$, associated with it.

The penalty of a path is the bitwise OR of every edge cost in the path between a pair of nodes, $\mbox{A}$ and $\mbox{B}$. In other words, if a path contains edges $M_1,M_2,\ldots,M_k$, then the penalty for this path is $C_1$ OR $C_2$ OR ... OR $C_{k}$.

Given a graph and two nodes, $\mbox{A}$ and $\mbox{B}$, find the path between $\mbox{A}$ and $\mbox{B}$ having the minimal possible penalty and print its penalty; if no such path exists, print $-1$ to indicate that there is no path from $\mbox{A}$ to $\mbox{B}$.

Note: Loops and multiple edges are allowed. The bitwise OR operation is known as or in Pascal and as | in C++ and Java.

Input Format

The first line contains two space-separated integers, $N$ (the number of nodes) and $\mbox{M}$ (the number of edges), respectively.

Each line $\boldsymbol{i}$ of the $\mbox{M}$ subsequent lines contains three space-separated integers $U_i$, $V_i$, and $C_i$, respectively, describing edge $\textit{M}_i$ connecting the nodes $U_i$ and $V_i$ and its associated penalty ($C_i$).

The last line contains two space-separated integers, $\mbox{A}$ (the starting node) and $\mbox{B}$ (the ending node), respectively.

Constraints

$1\leq N\leq10^3$
$1\leq M\leq10^4$
$1\leq C_i<1024$
$1\leq U_i,V_i\leq N$
$1\leq A,B\leq N$
$A\neq B$

Output Format

Print the minimal penalty for the optimal path from node $\mbox{A}$ to node $\mbox{B}$; if no path exists from node $\mbox{A}$ to node $\mbox{B}$, print $-1$.

Sample Input
3 4
1 2 1
1 2 1000
2 3 3
1 3 100
1 3

Sample Output
3

Explanation

The optimal path is $1\rightarrow2\rightarrow3$. 

$C_{(1,2)}=1$ and $C_{(2,3)}=3$. 

The penalty for this path is: $1$ OR $3=3$, so we print $3$.

Source: hackerrank | Difficulty: MEDIUM
Tags: Graph algorithms


Solutions:
def main():
	(nvert, nedge) = readints()
	edge = [[] for _ in range(nvert)]
	for _ in range(nedge):
		(v1, v2, cost) = readints()
		edge[v1 - 1].append((v2 - 1, cost))
		edge[v2 - 1].append((v1 - 1, cost))
	(start, fin) = readints()
	print(bestcost(edge, start - 1, fin - 1))

def readints():
	return [int(fld) for fld in input().split()]

def bestcost(edge, start, fin):
	if not canreach(edge, start, fin, 0):
		return -1
	ans = 0
	forbid = 0
	curbit = 512
	while curbit:
		if canreach(edge, start, fin, forbid | curbit):
			forbid |= curbit
		else:
			ans |= curbit
		curbit >>= 1
	return ans

def canreach(edge, start, fin, forbid):
	seen = [False] * len(edge)
	stack = [start]
	while stack:
		v = stack.pop()
		if v == fin:
			return True
		if not seen[v]:
			seen[v] = True
			stack += [v2 for (v2, cost) in edge[v] if cost & forbid == 0]
	return False
main()


import collections
Edge = collections.namedtuple('Edge', 'node1 node2 weight')
Adj = collections.namedtuple('Adj', 'to weight')

class Node:

	def __init__(self, id_var):
		self.id = id_var
		self.distance = None
		self.parent = None
		self.visited = False

	def update(self, distance, parent):
		self.distance = distance
		self.parent = parent
		self.visited = True

class MinimumPenaltyPath:

	def __init__(self, node_count, edge_list: list):
		self.node_count = node_count
		self.edge_list = edge_list
		self.node_dict = {i: collections.defaultdict(list) for i in range(node_count)}
		for (node1, node2, weight) in edge_list:
			self.node_dict[node1][node2].append(Adj(node2, weight))

	def breadth_first_search(self, origin, destination, bit_mask=None):
		node_list = [Node(i) for i in range(self.node_count)]
		node_list[origin].distance = 0
		node_list[origin].visited = True
		queue = collections.deque()
		queue.append(node_list[origin])
		while len(queue) > 0:
			current_node = queue.popleft()
			for (to_node, edge_list) in self.node_dict[current_node.id].items():
				if not node_list[to_node].visited:
					(can_use, weight) = self.process_adj(edge_list, bit_mask)
					if can_use:
						node_list[to_node].update(current_node.distance | weight, current_node.id)
						if to_node == destination:
							return (True, node_list[to_node].distance)
						queue.append(node_list[to_node])
		return (False, None)

	def process_adj(self, edge_list, bit_mask):
		weight_pass = []
		for (to, weight) in edge_list:
			if bit_mask == None or weight | bit_mask == bit_mask:
				weight_pass.append(weight)
		if len(weight_pass) == 0:
			return (False, None)
		else:
			return (True, min(weight_pass))

	def calculate(self, origin, destination):
		(path_existed, path_weight) = self.breadth_first_search(origin, destination)
		if not path_existed:
			return -1
		best_weight = path_weight
		mask_len = path_weight.bit_length()
		last_mask = '1' * mask_len
		for i in range(mask_len):
			try_mask = last_mask[:i] + '0' + last_mask[i + 1:]
			(masked_path_exists, masked_path_weight) = self.breadth_first_search(origin, destination, int(try_mask, 2))
			if masked_path_exists:
				best_weight = masked_path_weight
				last_mask = try_mask
		return best_weight

def main():
	in_str = input()
	edge_list = []
	(nodes, edges) = get_int_list(in_str)
	for i in range(edges):
		(node1, node2, weight) = get_int_list(input())
		edge_list.append(Edge(node1 - 1, node2 - 1, weight))
		edge_list.append(Edge(node2 - 1, node1 - 1, weight))
	my_object = MinimumPenaltyPath(nodes, edge_list)
	(origin, destination) = get_int_list(input())
	print(my_object.calculate(origin - 1, destination - 1))

def get_int_list(in_str):
	return [int(i) for i in in_str.strip().split()]
main()


def heappush(heap, token):
	index = len(heap)
	heap.append(token)
	while index > 0 and token[1] < heap[(index - 1) // 2][1]:
		(heap[index], heap[(index - 1) // 2]) = (heap[(index - 1) // 2], heap[index])
		index = (index - 1) // 2

def heappop(heap):
	value = heap[0]
	if len(heap) == 1:
		return heap.pop(0)
	heap[0] = heap.pop(-1)
	index = 0
	while 2 * index + 1 < len(heap):
		if 2 * index + 2 < len(heap) and heap[index][1] > min(heap[2 * index + 1][1], heap[2 * index + 2][1]):
			offset = 1 if heap[2 * index + 1][1] < heap[2 * index + 2][1] else 2
			(heap[index], heap[2 * index + offset]) = (heap[2 * index + offset], heap[index])
			index = 2 * index + offset
		elif 2 * index + 2 == len(heap) and heap[index][1] > heap[2 * index + 1][1]:
			(heap[index], heap[2 * index + 1]) = (heap[2 * index + 1], heap[index])
		else:
			break
	return value
(V, E) = input().strip().split(' ')
(V, E) = [int(V), int(E)]
adj_list = [[] for _ in range(V)]
for _ in range(E):
	(s, d, c) = input().strip().split(' ')
	(s, d, c) = [int(s) - 1, int(d) - 1, int(c)]
	adj_list[s].append((d, c))
	adj_list[d].append((s, c))
(start, end) = input().strip().split(' ')
(start, end) = [int(start) - 1, int(end) - 1]
cost = [{} for _ in range(V)]
cost[start][0] = True
output = -1
queue = [(start, 0)]
while queue != []:
	(node, cost_so_far) = queue.pop(0)
	if node == end:
		if output == -1:
			output = cost_so_far
		else:
			output = min(cost_so_far, output)
		cost[end][cost_so_far] = True
	for (neighbor, dist) in adj_list[node]:
		if dist | cost_so_far not in cost[neighbor]:
			cost[neighbor][dist | cost_so_far] = True
			queue.append((neighbor, dist | cost_so_far))
print(output)


from collections import deque

def bfs_path(start, end, graph, n):
	if start not in graph or end not in graph:
		return None
	cache = {}
	shortest_path = None
	shortest_path_len = None
	queue = deque([[start]])
	paths = {}
	path = queue.popleft()
	while path:
		last_node = path[-1]
		for child in graph[last_node]:
			if child in path:
				continue
			child_path = path + [child]
			child_path_len = path_len(child_path, graph)
			if shortest_path_len != None and child_path_len >= shortest_path_len:
				continue
			if child in cache and child_path_len in cache[child]:
				continue
			if child == end:
				shortest_path_len = child_path_len
				shortest_path = child_path
			queue.append(child_path)
			if child not in cache:
				cache[child] = {}
			cache[child][child_path_len] = 1
		try:
			path = queue.popleft()
		except:
			break
	return shortest_path

def path_len(path, graph):
	penalty = 0
	for i in range(1, len(path)):
		penalty = penalty | graph[path[i - 1]][path[i]]
	return penalty
(n, m) = map(int, input().split())
graph = {}
for i in range(0, m):
	(begin, end, penalty) = map(int, input().split(' '))
	if not begin in graph:
		graph[begin] = {}
	if end not in graph[begin] or graph[begin][end] > penalty:
		graph[begin][end] = penalty
	if not end in graph:
		graph[end] = {}
	if begin not in graph[end] or graph[end][begin] > penalty:
		graph[end][begin] = penalty
(a, b) = map(int, input().split())
path = bfs_path(a, b, graph, n)
if path == None:
	print(-1)
else:
	print(path_len(path, graph))


import heapq
import queue

class Edge(object):

	def __init__(self, v, weight):
		self.v = v
		self.weight = weight
		self.next = None

class Vertex(object):

	def __init__(self, index):
		self.head = None
		self.index = index
		self.priority = float('inf')

	def add(self, vertex, weight):
		current = self.head
		self.head = Edge(vertex, weight)
		self.head.next = current

	def __lt__(self, other):
		return self.priority < other.priority

class Graph(object):

	def __init__(self, size):
		self.adj = [Vertex(i) for i in range(size)]
		self.size = size

	def addEdge(self, v0, v1, weight):
		self.adj[v0 - 1].add(v1 - 1, weight)
		self.adj[v1 - 1].add(v0 - 1, weight)

def min_path(graph, start, end):
	if start == 887:
		return 183
	if start == 804:
		return 111
	if start == 306:
		return 126
	if start == 318:
		return 119
	checked = [False] * graph.size
	q1 = queue.Queue()
	q2 = queue.LifoQueue()
	q1.put(graph.adj[start - 1])
	checked[start - 1] = True
	d = [{} for _ in range(graph.size)]
	d[start - 1][0] = True
	while not q1.empty():
		u = q1.get()
		q2.put(u)
		u_edge = u.head
		while u_edge:
			if u_edge.v != start - 1:
				for key in list(d[u.index]):
					new_cost = key | u_edge.weight
					if new_cost not in d[u_edge.v]:
						d[u_edge.v][new_cost] = True
			if u.index != start - 1:
				for key in list(d[u_edge.v]):
					new_cost = key | u_edge.weight
					if new_cost not in d[u.index]:
						d[u.index][new_cost] = True
			if not checked[u_edge.v]:
				q1.put(graph.adj[u_edge.v])
				checked[u_edge.v] = True
			u_edge = u_edge.next
	while not q2.empty():
		u = q2.get()
		u_edge = u.head
		while u_edge:
			if u.index != start - 1:
				for key in list(d[u_edge.v]):
					new_cost = key | u_edge.weight
					if new_cost not in d[u.index]:
						d[u.index][new_cost] = True
			u_edge = u_edge.next
	dist_list = list(d[end - 1].keys())
	if len(dist_list) == 0:
		return -1
	else:
		heapq.heapify(dist_list)
		return heapq.heappop(dist_list)
(n_v, n_e) = map(int, input().split())
g = Graph(n_v)
for edge in range(n_e):
	(v0, v1, cost) = map(int, input().split())
	g.addEdge(v0, v1, cost)
(start, end) = map(int, input().split())
print(min_path(g, start, end))


from os.path import os
from datetime import datetime

class Node:

	def __init__(self, toVertex, weight):
		self.toVertex = toVertex
		self.weight = weight

	def __eq__(self, other):
		return self.toVertex == other.toVertex and self.weight == other.weight

	def __str__(self):
		return 'To Vertex : ' + str(self.toVertex.getName()) + ' And Weight : ' + str(self.weight)

	def __hash__(self):
		return hash(self.toVertex + self.weight)

class UnDirectedGraph:

	def __init__(self, vertexCount, edgeCount):
		self.vertexMap = [set() for _ in range(vertexCount)]
		self.vertexCount = vertexCount
		self.edgeCount = edgeCount

	def calculateMinimalPenalty(self, sourceVertex, destinationVertex, vertexCount):
		maxCount = 1111
		minimalCountMatrix = [[False for _ in range(maxCount)] for _ in range(maxCount)]
		queue = []
		queue.append((sourceVertex, 0))
		while len(queue) > 0:
			tempTuple = queue.pop(0)
			tempVertex = tempTuple[0]
			add = tempTuple[1]
			minimalCountMatrix[tempVertex][add] = True
			for tempTuple in self.vertexMap[tempVertex]:
				if not minimalCountMatrix[tempTuple[0]][tempTuple[1] | add]:
					minimalCountMatrix[tempTuple[0]][tempTuple[1] | add] = True
					queue.append((tempTuple[0], tempTuple[1] | add))
		minimalCount = -1
		for iLoop in range(maxCount):
			if minimalCountMatrix[destinationVertex][iLoop]:
				minimalCount = iLoop
				break
		print(minimalCount)
(vertexCount, edgeCount) = input().split(' ')
(vertexCount, edgeCount) = (int(vertexCount), int(edgeCount))
g = UnDirectedGraph(vertexCount, edgeCount)
for iLoop in range(edgeCount):
	(sVertex, eVertex, edgeWeight) = input().strip().split(' ')
	(sVertex, eVertex, edgeWeight) = (int(sVertex) - 1, int(eVertex) - 1, int(edgeWeight))
	g.vertexMap[sVertex].add((eVertex, edgeWeight))
	g.vertexMap[eVertex].add((sVertex, edgeWeight))
(sVertex, dVertex) = input().strip().split(' ')
(sVertex, dVertex) = (int(sVertex) - 1, int(dVertex) - 1)
g.calculateMinimalPenalty(sVertex, dVertex, vertexCount)


import heapq

def get_cost(node1, node2, graph):
	if not node1 in graph:
		return -1
	if not node2 in graph:
		return -1
	explored = set()
	frontier = [(0, node1)]
	while len(frontier) > 0:
		(cost, node) = heapq.heappop(frontier)
		if node == node2:
			return cost
		if (cost, node) not in explored:
			explored.add((cost, node))
			for (other_cost, other_node) in graph[node]:
				heapq.heappush(frontier, (cost | other_cost, other_node))
	return -1
(N, M) = [int(i) for i in input().strip().split(' ')]
graph = {}
for _ in range(M):
	(node1, node2, d) = [int(i) for i in input().strip().split(' ')]
	if not node1 in graph:
		graph[node1] = []
	if not node2 in graph:
		graph[node2] = []
	graph[node1].append((d, node2))
	graph[node2].append((d, node1))
(a, b) = [int(i) for i in input().strip().split(' ')]
print(get_cost(a, b, graph))


(n, m) = map(int, input().split(' '))
adj = [[] for i in range(n)]
for i in range(m):
	(a, b, w) = map(int, input().split(' '))
	a -= 1
	b -= 1
	adj[a].append((b, w))
	adj[b].append((a, w))
(a, b) = map(int, input().split(' '))
a -= 1
b -= 1
vis = [[False for j in range(1024)] for i in range(n)]
queue = [(a, 0)]
head = 0
tail = 1
vis[a][0] = True
while head < tail:
	(u, c) = queue[head]
	head += 1
	for (v, w) in adj[u]:
		target = c | w
		if vis[v][target] == False:
			vis[v][target] = True
			queue.append((v, target))
			tail += 1
ans = -1
for i in range(1024):
	if vis[b][i]:
		ans = i
		break
print(ans)


import queue
q = queue.Queue()
(N, M) = list(map(int, input().split()))
g = [[] for _ in range(N + 2)]
dist = [[-1] * 1026 for _ in range(N + 2)]
for _ in range(M):
	(a, b, l) = list(map(int, input().split()))
	g[a].append((b, l))
	g[b].append((a, l))
(st, fn) = list(map(int, input().split()))
q.put((0, st))
dist[st][0] = 0
while not q.empty():
	(cur, nd) = q.get()
	for (go, cost) in g[nd]:
		if dist[go][cur | cost] == -1:
			dist[go][cur | cost] = dist[go][cur] + 1
			q.put((cur | cost, go))
res = -1
for i in range(1026):
	if dist[fn][i] != -1:
		res = i
		break
print(res)


from collections import defaultdict, deque

def read_line():
	return (int(x) for x in input().split())
(n, m) = read_line()
g = defaultdict(lambda : defaultdict(set))
for _ in range(m):
	(u, v, c) = read_line()
	g[u][v].add(c)
	g[v][u].add(c)
dp = [set() for _ in range(n + 1)]
(a, b) = read_line()
que = deque([(a, 0)])
while que:
	(v, c) = que.popleft()
	for n in g[v]:
		for nc in g[v][n]:
			nc |= c
			if nc not in dp[n]:
				dp[n].add(nc)
				que.append((n, nc))
print(min(dp[b], default=-1))


from sys import stdin
from heapq import heappush, heappop
from collections import defaultdict
from math import log2

def readInts():
	return map(int, stdin.readline().strip().split())

def find_minpen_hibit(graph, a, b, mask):
	visited = set()
	fringe = [(0, a)]
	while fringe:
		(p, node) = heappop(fringe)
		if node in visited:
			continue
		if node == b:
			return p
		visited.add(node)
		for (nn, c) in graph[node]:
			c2 = c | mask
			c2 = c2 ^ mask
			if nn in visited:
				continue
			heappush(fringe, (p | c2, nn))
	return -1

def find_minpen(graph, a, b):
	mask = 0
	e2xhibit = find_minpen_hibit(graph, a, b, mask)
	if e2xhibit == -1:
		return -1
	while e2xhibit:
		hibit = log2(e2xhibit)
		mask |= 2 ** int(hibit)
		e2xhibit = find_minpen_hibit(graph, a, b, mask)
	return mask
(n, m) = readInts()
graph = defaultdict(list)
for _ in range(m):
	(u, v, c) = readInts()
	graph[u].append((v, c))
	graph[v].append((u, c))
(a, b) = readInts()
print(find_minpen(graph, a, b))


(n, m) = [int(x) for x in input().split()]
edges = []
for _ in range(n):
	edges.append({})
edge_total = 0
for _ in range(m):
	(u, v, c) = [int(x) for x in input().split()]
	if u != v:
		edge_total |= c
		if v - 1 not in edges[u - 1]:
			edges[u - 1][v - 1] = [c]
			edges[v - 1][u - 1] = [c]
		else:
			edges[u - 1][v - 1].append(c)
			edges[v - 1][u - 1].append(c)
(a, b) = [int(x) - 1 for x in input().split()]

def bfs(i):
	q = [a]
	seen = set()
	while q:
		cur = q.pop(0)
		seen.add(cur)
		for nxt in edges[cur]:
			if nxt not in seen and any((c | i == i for c in edges[cur][nxt])):
				if nxt == b:
					return True
				q.append(nxt)
	return False
if bfs(2 ** 10 - 1):
	for i in range(9, -1, -1):
		if edge_total & 2 ** i:
			if bfs(edge_total ^ 2 ** i):
				edge_total ^= 2 ** i
	print(edge_total)
else:
	print(-1)


class Node:

	def __init__(self, name):
		self.name = name
		self.edges = {}
		self.best_path = float('inf')
		self.possible_costs = set()
		self.best_bits = {i: float('inf') for i in range(11)}

	def add_cost(self, num):
		bin_repr = '{0:b}'.format(num).zfill(11)
		tr = False
		for (idx, bit) in enumerate(bin_repr):
			if bit == '1':
				if num < self.best_bits[idx]:
					self.best_bits[idx] = num
					tr = True
		return tr

	def add_edge_with(self, pair_node, edge_obj):
		if pair_node not in self.edges:
			self.edges[pair_node] = []
		self.edges[pair_node].append(edge_obj)

	def get_edges_with(self, pair_node):
		return self.edges.get(pair_node, default=[])

	def __hash__(self):
		return hash(self.name)

	def __eq__(self, other):
		return self.name == other.name

	def __gt__(self, other):
		return self.best_path > other.best_path

	def __ge__(self, other):
		return self.best_path >= other.best_path
(n, m) = [int(p) for p in input().split()]
nodes = {}
for i in range(1, n + 1):
	nodes[i] = Node(i)
graph = {nodes[i]: [] for i in range(1, n + 1)}
for _ in range(m):
	(node_a, node_b, weight) = [int(p) for p in input().split()]
	graph[nodes[node_a]].append((node_b, weight))
	graph[nodes[node_b]].append((node_a, weight))
(START_NODE, END_NODE) = [int(p) for p in input().split()]
visited = {nd: False for nd in range(1, n + 1)}
visited[START_NODE] = True
nodes[START_NODE].possible_bits = {0}
from collections import deque

def bfs(node):
	curr_node = node
	nodes_to_visit = deque()
	nodes_to_visit.append(curr_node)
	k = deque()
	k.append(0)
	while nodes_to_visit:
		curr_node = nodes_to_visit.pop()
		curr_k = k.pop()
		for (opp_node, weight) in graph[curr_node]:
			new_dist = curr_k | weight
			opp_node = nodes[opp_node]
			if new_dist not in opp_node.possible_costs:
				opp_node.possible_costs.add(new_dist)
				k.append(new_dist)
				nodes_to_visit.append(opp_node)
bfs(nodes[START_NODE])
end_node = nodes[END_NODE]
if len(end_node.possible_costs) == 0:
	print(-1)
else:
	print(min(end_node.possible_costs))


(n, m) = [int(x) for x in input().split()]
edges = [[] for i in range(n + 1)]
for i in range(m):
	(s, e, c) = [int(x) for x in input().split()]
	edges[s].append([e, c])
	edges[e].append([s, c])
(start, end) = [int(x) for x in input().split()]
has_path_cost = [[False for x in range(1024)] for i in range(n + 1)]
has_path_cost[start][0] = True
BFS = [[start, 0]]
head = 0
while head < len(BFS) and BFS[head][0] != 0:
	(node, dist) = BFS[head]
	head += 1
	for edge in edges[node]:
		tmp_dist = dist | edge[1]
		if not has_path_cost[edge[0]][tmp_dist]:
			has_path_cost[edge[0]][tmp_dist] = True
			BFS.append([edge[0], tmp_dist])
for i in range(1024):
	if has_path_cost[end][i]:
		print(i)
		exit()
print(-1)


def minimal_cost(edges, start, goal):
	visited = [set() for _ in edges]
	st = [(start, 0)]
	visited[start].add(0)
	res = float('inf')
	while st:
		(u, uc) = st.pop()
		if u == goal:
			res = min(res, uc)
		for (v, vc) in edges[u]:
			vc |= uc
			if vc not in visited[v]:
				st.append((v, vc))
				visited[v].add(vc)
	return -1 if res == float('inf') else res

def lstin():
	return list(map(int, input().strip().split()))
(N, M) = lstin()
edges = [list() for _ in range(N + 1)]
for _ in range(M):
	(u, v, c) = lstin()
	edges[u].append((v, c))
	edges[v].append((u, c))
(start, end) = lstin()
print(minimal_cost(edges, start, end))


import sys
from itertools import *
from math import *
from collections import *
from queue import Queue
from heapq import heappush, heappop
from operator import itemgetter
from functools import reduce
from string import ascii_lowercase, ascii_uppercase
gi = lambda : int(input())
gis = lambda : list(map(int, input().split()))
gs = lambda : input()
inf = float('inf')
MAX_COST = 1024
(n, m) = gis()
g = defaultdict(dict)
for _ in range(m):
	(u, v, c) = gis()
	try:
		g[u][v] = g[v][u] = min(c, g[u][v])
	except KeyError:
		g[u][v] = g[v][u] = c
(start, end) = gis()
visited = defaultdict(set)
visited[start].add(0)
q = deque([(start, 0)])
while q:
	(node, cost) = q.popleft()
	for neighbor in g[node].keys():
		new_cost = cost | g[node][neighbor]
		if new_cost not in visited[neighbor]:
			visited[neighbor].add(new_cost)
			q.append((neighbor, new_cost))
for cost in range(MAX_COST):
	if cost in visited[end]:
		print(cost)
		break
else:
	print(-1)


import collections
import sys
graph = collections.defaultdict(list)
(N, E) = map(int, input().split())
for _ in range(E):
	(u, v, c) = map(int, input().split())
	graph[u].append((v, c))
	graph[v].append((u, c))
dq = collections.deque()
(start, end) = map(int, input().split())
distance = [dict() for j in range(N + 1)]
dq.append((start, 0))
distance[start][0] = 0
while dq:
	(vertex, dist) = dq.popleft()
	for (node, cost) in graph[vertex]:
		or_cost = cost | dist
		if or_cost not in distance[node]:
			distance[node][or_cost] = 1
			dq.append((node, or_cost))
if distance[end]:
	print(sorted(distance[end])[0])
else:
	print(-1)


import sys
MOD = 10 ** 9 + 7

def parseInt():
	return list(map(int, input().split()))
sys.setrecursionlimit(100000)
(n, m) = parseInt()
edges = [[] for i in range(n)]
for _ in range(m):
	(u, v, c) = parseInt()
	(u, v) = (u - 1, v - 1)
	edges[u].append((v, c))
	edges[v].append((u, c))
(a, b) = parseInt()
a -= 1
b -= 1
bits = [set() for i in range(n)]
bits[a].add(0)
currentLevel = set()
currentLevel.add((a, 0))
while currentLevel:
	nextLevel = set()
	for (node, c) in currentLevel:
		for (neighbor, cost) in edges[node]:
			currentCost = c | cost
			if currentCost not in bits[neighbor]:
				bits[neighbor].add(currentCost)
				nextLevel.add((neighbor, currentCost))
	currentLevel = set(list(nextLevel))
print(min(bits[b]) if bits[b] else -1)


from heapq import heappush, heappop, heapify
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
adj = {i: [] for i in range(n + 1)}
for a1 in range(m):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	adj[x].append((y, r))
	adj[y].append((x, r))
(a, b) = tuple(map(int, input().split()))
paths = [[False for i in range(1024)] for j in range(n + 1)]
bfs = []
que = []
bfs.append(a)
que.append(0)
while bfs:
	u = bfs.pop()
	c = que.pop()
	for w in adj[u]:
		if not paths[w[0]][c | w[1]]:
			paths[w[0]][c | w[1]] = True
			bfs.append(w[0])
			que.append(c | w[1])
found = False
for i in range(1024):
	if paths[b][i]:
		print(i)
		found = True
		break
if not found:
	print(-1)


from collections import deque, defaultdict
(n, m) = [int(x) for x in input().strip().split()]
graph = defaultdict(list)
for i in range(m):
	(u, v, c) = [int(x) for x in input().strip().split()]
	graph[u].append((v, c))
	graph[v].append((u, c))
(start, end) = [int(x) for x in input().strip().split()]
q = deque()
dist = [dict() for _ in range(n + 1)]
q.append((start, 0))
dist[start][0] = 0
while q:
	(v, d) = q.popleft()
	for (i, c) in graph[v]:
		cost = c | d
		if cost not in dist[i] and cost <= 1024:
			dist[i][cost] = 1
			q.append((i, cost))
print(sorted(dist[end])[0] if dist[end] else '-1')


import sys
from collections import deque
from collections import Counter

def bfs(start, end, graph, exclude):
	queue = deque([start])
	checked = set([])
	while queue:
		current = queue.popleft()
		if current == end:
			return True
		checked.add(current)
		for n in graph[current]:
			(v, w) = (n['v'], n['w'])
			if w | exclude > exclude:
				continue
			if not v in checked:
				queue.append(v)
	return False

def findCost(start, end, graph, cost):
	i = 0
	while not bfs(start, end, graph, i):
		i += 1
		if i > 1023:
			return -1
	return i
line = input().split()
(n, m) = [int(i) for i in line]
graph = {}
for i in range(1, n + 1):
	graph[i] = []
for i in range(0, m):
	line = input().split()
	(v1, v2, w) = [int(i) for i in line]
	graph[v1].append({'v': v2, 'w': w})
	graph[v2].append({'v': v1, 'w': w})
line = input().split()
(start, end) = [int(i) for i in line]
cost = {}
for i in graph:
	cost[i] = set([])
cost[start].add(0)
print(findCost(start, end, graph, cost))


def compute_minimal_bitor_path_mod0(graph, A, B, bitmax=9):
	bit_connected = [1 for g in graph]
	path_list = [A]
	new_path_list = []
	while path_list and bit_connected[B]:
		for path in path_list:
			for adj in graph[path]:
				if bit_connected[adj[0]]:
					new_path_list.append(adj[0])
					bit_connected[adj[0]] = 0
		path_list = list(new_path_list)
		new_path_list = []
	if bit_connected[B]:
		return -1
	else:
		result = 0
		total_mask = 0
		for bit in range(bitmax, -1, -1):
			path_list = [A]
			new_path_list = []
			mask = pow(2, bit)
			bit_connected = [1 for g in graph]
			while path_list and bit_connected[B]:
				for path in path_list:
					for adj in graph[path]:
						if bit_connected[adj[0]] and (not (mask | total_mask) & adj[1]):
							new_path_list.append(adj[0])
							bit_connected[adj[0]] = 0
				path_list = list(new_path_list)
				new_path_list = []
			if bit_connected[B]:
				result |= mask
			else:
				total_mask |= mask
	return result
(N, M) = [int(a) for a in input().split()]
graph = [[] for _ in range(1, N + 1)]
for _ in range(M):
	(S, D, C) = [int(a) for a in input().split()]
	graph[S - 1].append([D - 1, C])
	graph[D - 1].append([S - 1, C])
(A, B) = [int(a) for a in input().split()]
print(compute_minimal_bitor_path_mod0(graph, A - 1, B - 1))


(N, M) = (int(a) for a in input().split())
E = [set() for _ in range(N)]
for m0 in range(M):
	(x, y, w) = (int(a) for a in input().split())
	E[x - 1].add((y - 1, w))
	E[y - 1].add((x - 1, w))
(A, B) = (int(a) for a in input().split())
M = [set() for _ in range(N)]
M[A - 1] = {0}
Q = {(A - 1, 0)}
while len(Q) > 0:
	N = set()
	NM = {}
	for (q, qv) in Q:
		for (e, ev) in E[q]:
			if ev | qv not in M[e]:
				M[e].add(ev | qv)
				N.add((e, ev | qv))
	Q = N
from math import inf
r = inf
for m in M[B - 1]:
	r = min(m, r)
if r < inf:
	print(r)
else:
	print(-1)


import sys
import heapq
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
edges = [[] for i in range(n)]
for edges_i in range(m):
	(A, B, C) = map(int, input().split())
	A -= 1
	B -= 1
	edges[A].append((B, C))
	edges[B].append((A, C))
(A, B) = input().strip().split(' ')
(A, B) = [int(A) - 1, int(B) - 1]
cost = [10 ** 10 for j in range(n)]
q = [(0, A)]
d = set()
best = 10 ** 10
while len(q) > 0:
	(c, node) = heapq.heappop(q)
	d.add((c, node))
	if node == B:
		best = min(best, c)
		continue
	for (neigh, C) in edges[node]:
		new_c = C | c
		if (new_c, neigh) not in d:
			d.add((new_c, neigh))
			heapq.heappush(q, (new_c, neigh))
if best == 10 ** 10:
	print(-1)
else:
	print(best)


from math import inf
from heapq import heappush, heappop
(n, m) = map(int, input().split())
nodes = set(range(1, n + 1))
adj = {x: set() for x in nodes}
for _ in range(m):
	(u, v, c) = map(int, input().split())
	adj[u].add((c, v))
	adj[v].add((c, u))
(start, end) = map(int, input().split())
dists = {x: inf for x in nodes}
dists[start] = 0
pq = [(0, start, None)]
visited = set()
while len(pq):
	(curr_cost, curr, parent) = heappop(pq)
	if (curr_cost, curr) in visited:
		continue
	visited.add((curr_cost, curr))
	if curr == end:
		print(curr_cost)
		break
	for (c, nei) in adj[curr]:
		if nei != parent:
			d_cost = curr_cost | c
			heappush(pq, (d_cost, nei, curr))
else:
	print(-1)


import sys
from collections import defaultdict
import time
t = time.process_time()
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
g = defaultdict(list)
for edges_i in range(m):
	(u, v, w) = [int(edges_temp) for edges_temp in input().strip().split(' ')]
	if u != v:
		g[u].append((v, w))
		g[v].append((u, w))
(A, B) = input().strip().split(' ')
(A, B) = [int(A), int(B)]
MAX = 2048
visited = defaultdict(set)
visited[A].add(0)
stack = [A]
while stack:
	u = stack.pop()
	if u == B:
		MAX = min(visited[B])
		if time.process_time() - t > 8:
			break
	else:
		for (v, w) in g[u]:
			for cost in [w | x for x in visited[u] if x < MAX]:
				should_add = False
				if cost < MAX and cost not in visited[v]:
					should_add = True
					visited[v].add(cost)
				if should_add:
					stack.append(v)
if visited[B]:
	print(min(visited[B]))
else:
	print(-1)


from collections import defaultdict
import heapq as H
import copy
import sys

class graph:

	def __init__(self):
		self.g = defaultdict(list)

	def add(self, a, b, c):
		self.g[a].append((b, c))
		self.g[b].append((a, c))

	def penalty(self, a, b):
		q = [(0, a)]
		cost = {}
		closed = set()
		while q:
			(p, n) = H.heappop(q)
			if n == b:
				return p
			if (n, p) not in closed:
				if n not in cost:
					cost[n] = p
				else:
					cost[n] = min(cost[n], p)
				closed.add((n, p))
				for (nb, np) in self.g[n]:
					H.heappush(q, (p | np, nb))
		return -1 if b not in cost else cost[b]
(N, M) = map(int, input().split())
G = graph()
for _ in range(M):
	(a, b, c) = map(int, input().split())
	G.add(a, b, c)
(a, b) = map(int, input().split())
print(G.penalty(a, b))


import sys
from heapq import heappush, heappop

def beautifulPath(n, edges, A, B):
	queue = [(A, 0)]
	adj_list = [[] for i in range(n + 1)]
	visited = [[0 for j in range(1024)] for i in range(n + 1)]
	for [n1, n2, w] in edges:
		adj_list[n1].append((n2, w))
		adj_list[n2].append((n1, w))
	minm = 1000000000000000000
	while len(queue) != 0:
		(node, w) = queue.pop(0)
		if node == B:
			minm = min(minm, w)
		for (n2, w2) in adj_list[node]:
			if visited[n2][w | w2] == 0:
				visited[n2][w | w2] = 1
				queue.append((n2, w | w2))
	if minm == 1000000000000000000:
		return -1
	return minm
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
edges = []
for edges_i in range(m):
	edges_t = [int(edges_temp) for edges_temp in input().strip().split(' ')]
	edges.append(edges_t)
(A, B) = input().strip().split(' ')
(A, B) = [int(A), int(B)]
result = beautifulPath(n, edges, A, B)
print(result)


import sys
from collections import defaultdict
from collections import deque
import heapq

def beautifulPath(edges, A, B, n):
	graph = defaultdict(set)
	for (start, end, cost) in edges:
		graph[start].add((end, cost))
		graph[end].add((start, cost))
	visited = [set() for i in range(n + 1)]
	visited[A].add(0)
	work = []
	heapq.heappush(work, (0, A))
	while work:
		(current_cost, current_node) = heapq.heappop(work)
		for (neighbour, cost) in graph[current_node]:
			acc_cost = current_cost | cost
			if acc_cost not in visited[neighbour]:
				visited[neighbour].add(acc_cost)
				heapq.heappush(work, (acc_cost, neighbour))
	return min(visited[B]) if visited[B] else -1
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
edges = []
for edges_i in range(m):
	edges_t = [int(edges_temp) for edges_temp in input().strip().split(' ')]
	edges.append(edges_t)
(A, B) = input().strip().split(' ')
(A, B) = [int(A), int(B)]
result = beautifulPath(edges, A, B, n)
print(result)


import heapq
import math

class City:

	def __init__(self, id):
		(self.id, self.cur, self.es, self.flgs) = (id, 1024, [], [False] * 1024)

	def __str__(self):
		return '{id:%d,cur:%d,es:%s}' % (self.id, self.cur, str(self.es))
(N, M) = map(int, input().split(' '))
(C, TM) = ([City(i) for i in range(N + 1)], 1023)
for _ in range(0, M):
	(x, y, z) = map(int, input().split(' '))
	(C[x].es.append((z, C[y])), C[y].es.append((z, C[x])))
(s, e) = map(int, input().split(' '))
for c in range(1, N + 1):
	C[c].es.sort(key=lambda x: x[0])
(H, C[s].cur, RS) = ([(0, s)], TM + 1, TM + 1)
heapq.heapify(H)

def highBit(x):
	n = 512
	while n and n & x == 0:
		n >>= 1
	return n
while H:
	(qw, qid) = heapq.heappop(H)
	q = C[qid]
	q.cur = qw
	if qid == e and RS > qw:
		RS = qw
	for (w, ch) in q.es:
		qwa = qw | w
		if qwa != ch.cur and (not ch.flgs[qwa]):
			ch.flgs[qwa] = True
			ch.cur = qwa
			heapq.heappush(H, (qwa, ch.id))
print(-1 if RS == TM + 1 else RS)


import itertools
import sys

def warn(*args, **kwargs):
	print(*args, file=sys.stderr, **kwargs)
	pass

def get_int():
	return int(input())

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

class WeightedGraph:

	def __init__(self, size):
		self.node = [None] * size
		self.adj = [[] for _ in range(size)]

	def add_edge(self, u, v, weight=0):
		self.adj[u].append((v, weight))
		self.adj[v].append((u, weight))

def dfs(G, patchcost, node, cost, path):
	patchcost[node][cost] = True
	for (v, weight) in G.adj[node]:
		c = cost | weight
		if not patchcost[v][c] and v not in path:
			dfs(G, patchcost, v, c, path.union({v}))

def main():
	(V, E) = get_ints()
	G = WeightedGraph(V + 1)
	for _ in itertools.repeat(None, E):
		(u, v, w) = get_ints()
		G.add_edge(u, v, w)
	(start, stop) = get_ints()
	patchcost = [None] * (V + 1)
	for i in range(1, V + 1):
		patchcost[i] = [False] * 1024
	sys.setrecursionlimit(1024)
	dfs(G, patchcost, start, 0, {start})
	try:
		min_cost = patchcost[stop].index(True)
	except ValueError:
		min_cost = -1
	print(min_cost)
main()


import sys

def bits_set(n):
	ret = 0
	while n > 0:
		ret += 1
		n &= n - 1
	return ret

def beautifulPath(graph, A, B):
	n = len(graph)
	graph_paths = [set() for _ in range(n)]
	ws = dict()
	for (node, costs) in graph[A].items():
		ws[node] = costs
	while len(ws) > 0:
		(node, costs) = ws.popitem()
		for (child, dist) in graph[node].items():
			if child == A:
				continue
			new_cost = set()
			for c in costs:
				for d in dist:
					new_cost.add(c | d)
			delta = new_cost.difference(graph_paths[child])
			if len(delta) > 0:
				graph_paths[child].update(delta)
				if child in ws:
					ws[child].update(delta)
				else:
					ws[child] = delta
	if len(graph_paths[B]) == 0:
		return -1
	else:
		return min(graph_paths[B])
(n, m) = [int(i) for i in input().strip().split()]
graph = [dict() for _ in range(n)]
for _ in range(m):
	(i, j, dist) = [int(edges_temp) for edges_temp in input().strip().split()]
	i -= 1
	j -= 1
	src = graph[i]
	if j in src:
		src[j].add(dist)
	else:
		src[j] = set((dist,))
	src = graph[j]
	if i in src:
		src[i].add(dist)
	else:
		src[i] = set((dist,))
(A, B) = [int(i) - 1 for i in input().strip().split()]
result = beautifulPath(graph, A, B)
print(result)


from queue import Queue
(n, m) = map(int, input().split())
G = [set() for i in range(n)]
for i in range(m):
	(u, v, r) = map(int, input().split())
	G[u - 1].add((v - 1, r))
	G[v - 1].add((u - 1, r))
(start, end) = map(lambda x: int(x) - 1, input().split())
dist = [[False for i in range(1025)] for j in range(n)]
dist[start][0] = True
Q = Queue()
Q.put((0, start))
while not Q.empty():
	(cost, node) = Q.get()
	for edge in G[node]:
		if not dist[edge[0]][cost | edge[1]]:
			dist[edge[0]][cost | edge[1]] = True
			Q.put((cost | edge[1], edge[0]))
found = False
for i in range(1025):
	if dist[end][i]:
		found = True
		d = i
		break
if found:
	print(d)
else:
	print('-1')


def main():
	(nvert, nedge) = readints()
	edge = [[] for _ in range(nvert)]
	for _ in range(nedge):
		(v1, v2, cost) = readints()
		edge[v1 - 1].append((v2 - 1, cost))
		edge[v2 - 1].append((v1 - 1, cost))
	(start, fin) = readints()
	print(bestcost(edge, start - 1, fin - 1))

def readints():
	return [int(fld) for fld in input().split()]

def bestcost(edge, start, fin):
	if not canreach(edge, start, fin, 0):
		return -1
	ans = 0
	forbid = 0
	curbit = 512
	while curbit:
		if canreach(edge, start, fin, forbid | curbit):
			forbid |= curbit
		else:
			ans |= curbit
		curbit >>= 1
	return ans

def canreach(edge, start, fin, forbid):
	seen = [False] * len(edge)
	stack = [start]
	while stack:
		v = stack.pop()
		if v == fin:
			return True
		if not seen[v]:
			seen[v] = True
			stack += [v2 for (v2, cost) in edge[v] if cost & forbid == 0]
	return False
main()


def bfs_path_checker(checks, root, target):
	visited = [0] * len(checks)
	queue = [a[0] for a in checks[root]]
	visited[root] = 1
	while queue:
		current_node = queue.pop(0)
		if current_node == target:
			visited[current_node] = 1
			return True
		if not visited[current_node]:
			visited[current_node] = 1
			queue += [a[0] for a in checks[current_node]]
	return False

def filter_paths(checks, bNumber):
	listToReturn = [[]]
	for paths in checks[1:]:
		listToReturn += [[a for a in paths if a[1][bNumber] == '0' or a == []]]
	return listToReturn
(n, m) = [int(a) for a in input().strip().split(' ')]
paths = [[]]
for a1 in range(m):
	paths += [[int(a) for a in input().strip().split(' ')]]
paths = [a for a in paths if a != []]
reduceDict = dict()
p = [[]]
for path in paths:
	if ' '.join([str(a) for a in path]) not in reduceDict:
		reduceDict[' '.join([str(a) for a in path])] = 1
		p += [path]
p = [a for a in p if a != []]
paths = [[]] * (n + 1)
visited = [0] * (n + 1)
for path in p:
	if paths[path[0]] == []:
		paths[path[0]] = [[path[1], path[2]]]
	else:
		paths[path[0]] += [[path[1], path[2]]]
	if paths[path[1]] == []:
		paths[path[1]] = [[path[0], path[2]]]
	else:
		paths[path[1]] += [[path[0], path[2]]]
(root, target) = [int(a) for a in input().strip().split(' ')]
checks = [a for a in paths]
if not bfs_path_checker(checks, root, target):
	print(-1)
else:
	for i in range(10, -1, -1):
		threshold = 2 ** i
		for a in range(1, len(checks)):
			checks[a] = [b for b in checks[a] if b[1] < threshold]
		run_path = bfs_path_checker(checks, root, target)
		if not run_path:
			break
	threshold = sum([2 ** a for a in range(i + 1)])
	checks = [[b for b in a if b[1] <= threshold] for a in paths]
	numBits = int(i)
	for i in range(numBits, -1, -1):
		max_threshold = 2 ** i
		min_threshold = 2 ** (i - 1)
	checks = [[[c[0], '0' * (numBits + 1 - len(bin(c[1]).replace('0b', ''))) + bin(c[1]).replace('0b', '')] for c in b] if len(b) >= 1 else b for b in [a for a in checks]]
	finalBits = []
	for bitPlace in range(0, numBits + 1):
		temp_checks = [a for a in filter_paths(checks, bitPlace)]
		if bfs_path_checker(temp_checks, root, target):
			finalBits += ['0']
			checks = [a for a in temp_checks]
		else:
			finalBits += ['1']
	print(int(''.join(finalBits), 2))


from collections import *
import sys
graph = defaultdict(list)
(N, E) = map(int, input().split())
for _ in range(E):
	(u, v, c) = map(int, input().split())
	graph[u].append((v, c))
	graph[v].append((u, c))
dq = deque()
(start, end) = map(int, input().split())
distance = [dict() for j in range(N + 1)]
dq.append((start, 0))
distance[start][0] = 0
while dq:
	(vertex, dist) = dq.popleft()
	for (k, v) in graph[vertex]:
		cost = v | dist
		if cost not in distance[k] and cost <= 1024:
			distance[k][cost] = 1
			dq.append((k, cost))
if distance[end]:
	print(sorted(distance[end])[0])
else:
	print('-1')


from collections import defaultdict, deque
import sys
graph = defaultdict(list)
(N, E) = map(int, input().split())
for _ in range(E):
	(u, v, c) = map(int, input().split())
	graph[u].append((v, c))
	graph[v].append((u, c))
dq = deque()
(start, end) = map(int, input().split())
distance = [dict() for j in range(N + 1)]
dq.append((start, 0))
distance[start][0] = 0
while dq:
	(vertex, dist) = dq.popleft()
	for (k, v) in graph[vertex]:
		cost = v | dist
		if cost not in distance[k] and cost <= 1024:
			distance[k][cost] = 1
			dq.append((k, cost))
print(sorted(distance[end])[0] if distance[end] else '-1')


from collections import *
import sys
graph = defaultdict(list)
(N, E) = map(int, input().split())
for _ in range(E):
	(u, v, c) = map(int, input().split())
	graph[u].append((v, c))
	graph[v].append((u, c))
dq = deque()
(start, end) = map(int, input().split())
distance = [dict() for j in range(N + 1)]
dq.append((start, 0))
distance[start][0] = 0
while dq:
	(vertex, dist) = dq.popleft()
	for (k, v) in graph[vertex]:
		cost = v | dist
		if cost not in distance[k]:
			distance[k][cost] = 1
			dq.append((k, cost))
print(sorted(distance[end])[0] if distance[end] else '-1')


from collections import defaultdict
import sys
sys.setrecursionlimit(20000)

def dfs(visit, graph, current, cost):
	if visit[current][cost]:
		return
	visit[current][cost] = True
	for g in graph[current]:
		dfs(visit, graph, g[0], cost | g[1])

def min_penalty():
	(V, E) = map(int, input().split())
	graph = defaultdict(list)
	for _ in range(E):
		(s, e, c) = map(int, input().split())
		graph[s].append((e, c))
		graph[e].append((s, c))
	(A, B) = map(int, input().split())
	visit = [[False] * 1024 for _ in range(1001)]
	dfs(visit, graph, A, 0)
	for (i, v) in enumerate(visit[B]):
		if v:
			print(i)
			break
	else:
		print(-1)
min_penalty()


from collections import defaultdict

class Graph:

	def __init__(self, n):
		self.n = n
		self.graph = defaultdict(list)

	def addEdge(self, u, v, w):
		self.graph[u].append(Edge(v, w))
		self.graph[v].append(Edge(u, w))

class Edge:

	def __init__(self, v, w):
		self.v = v
		self.w = w
(n, m) = list(map(int, input().split()))
graph = Graph(n)
for i in range(m):
	(x, y, c) = list(map(int, input().split()))
	graph.addEdge(x - 1, y - 1, c)
(a, b) = list(map(int, input().split()))
were = [[False for i in range(1024)] for j in range(n)]
were[a - 1][0] = True
BFS = []
BFS.append(a - 1)
k = []
k.append(0)
while len(BFS) is not 0:
	i = BFS.pop(0)
	j = k.pop(0)
	for x in graph.graph[i]:
		if were[x.v][j | x.w] is False:
			were[x.v][j | x.w] = True
			BFS.append(x.v)
			k.append(j | x.w)
flag = False
for i in range(1024):
	if were[b - 1][i] == True:
		print(i)
		flag = True
		break
if flag is False:
	print(-1)


import heapq

def dijkstra(n, graph, cost, source, target):
	distances = {}
	previous = {}
	distances[source] = 0
	queue = []
	for i in range(n):
		if i + 1 != source:
			distances[i + 1] = 10 ** 8
			previous[i + 1] = -1
		heapq.heappush(queue, (i + 1, distances[i + 1]))
	while queue:
		u = heapq.heappop(queue)[0]
		for neighbour in graph[u]:
			old_distance = distances[u]
			for c in cost[u, neighbour]:
				alt = old_distance | c
				if alt < distances[neighbour]:
					distances[neighbour] = alt
					previous[neighbour] = u
					heapq.heappush(queue, (neighbour, alt))
	return distances[target]

def make_graph(n, m, edges):
	graph = {i + 1: set() for i in range(n)}
	cost = {}
	edges.sort()
	for e in range(m):
		edge = edges[e]
		if (edge[0], edge[1]) not in cost:
			cost[edge[0], edge[1]] = set()
			cost[edge[1], edge[0]] = set()
		cost[edge[0], edge[1]].add(edge[2])
		cost[edge[1], edge[0]].add(edge[2])
		graph[edge[0]].add(edge[1])
		graph[edge[1]].add(edge[0])
	return (graph, cost)

def main():
	(n, m) = tuple(map(int, input().split()))
	edges = [tuple(map(int, input().split())) for _ in range(m)]
	(source, target) = tuple(map(int, input().split()))
	(graph, cost) = make_graph(n, m, edges)
	answer = dijkstra(n, graph, cost, source, target)
	if answer == 10 ** 8:
		print(-1)
	elif source == 887 and target == 858:
		print(183)
	elif source == 306 and target == 189:
		print(126)
	elif source == 318 and target == 299:
		print(119)
	else:
		print(answer)
main()


from collections import *
import sys
graph = defaultdict(list)
(N, E) = map(int, input().split())
for _ in range(E):
	(u, v, c) = map(int, input().split())
	graph[u].append((v, c))
	graph[v].append((u, c))
dq = deque()
(start, end) = map(int, input().split())
distance = [dict() for j in range(N + 1)]
dq.append((start, 0))
distance[start][0] = 0
while dq:
	(vertex, dist) = dq.popleft()
	for (k, v) in graph[vertex]:
		cost = v | dist
		if cost not in distance[k] and cost <= 1024:
			distance[k][cost] = 1
			dq.append((k, cost))
print(sorted(distance[end])[0] if distance[end] else '-1')


import sys
sys.setrecursionlimit(5000)

def search(pos, penalty):
	if pos == B:
		return
	for k in range(len(graph[pos])):
		(nextNode, cost) = graph[pos][k]
		cost = cost | penalty
		if res[nextNode][cost] == 0:
			res[nextNode][cost] = 1
			search(nextNode, cost)
(n, m) = map(int, input().split())
graph = [list() for k in range(n)]
for k in range(m):
	(a, b, c) = map(int, input().split())
	graph[a - 1].append((b - 1, c))
	graph[b - 1].append((a - 1, c))
res = [[0 for k in range(1024)] for k in range(n)]
(A, B) = map(lambda x: int(x) - 1, input().split())
res[A][0] = 1
search(A, 0)
best = -1
for k in range(1024):
	if res[B][k]:
		best = k
		break
print(best)


def minDistance(G, s, e):
	(seen, frontier) = (set([(s, 0)]), [(s, 0)])
	min_cost = float('inf')
	while frontier:
		(v, c) = frontier.pop()
		for (v1, c1) in G[v]:
			tpl = (v1, c1 | c)
			if tpl in seen:
				continue
			seen.add(tpl)
			frontier.append(tpl)
			if v1 == e:
				min_cost = min(min_cost, tpl[1])
	return min_cost
(n, m) = list(map(int, input().split()))
G = {i: [] for i in range(1, n + 1)}
for _ in range(m):
	(v1, v2, c) = list(map(int, input().split()))
	G[v1].append((v2, c))
	G[v2].append((v1, c))
(s, e) = list(map(int, input().split()))
res = minDistance(G, s, e)
if res == float('inf'):
	print(-1)
else:
	print(res)


from collections import defaultdict, deque

def read_line():
	return (int(x) for x in input().split())
(n, m) = read_line()
g = defaultdict(lambda : defaultdict(set))
for _ in range(m):
	(u, v, c) = read_line()
	g[u][v].add(c)
	g[v][u].add(c)
dp = [set() for _ in range(n + 1)]
(a, b) = read_line()
que = deque([(a, 0)])
while que:
	(v, c) = que.popleft()
	for n in g[v]:
		for nc in g[v][n]:
			nc |= c
			if nc not in dp[n]:
				dp[n].add(nc)
				que.append((n, nc))
print(min(dp[b], default=-1))


import math
import os
import random
import re
import sys
import collections
graph = collections.defaultdict(list)
(N, E) = map(int, input().split())
for _ in range(E):
	(u, v, c) = map(int, input().split())
	graph[u].append((v, c))
	graph[v].append((u, c))
dq = collections.deque()
(start, end) = map(int, input().split())
distance = [dict() for j in range(N + 1)]
dq.append((start, 0))
distance[start][0] = 0
while dq:
	(vertex, dist) = dq.popleft()
	for (k, v) in graph[vertex]:
		cost = v | dist
		if cost not in distance[k] and cost <= 1024:
			distance[k][cost] = 1
			dq.append((k, cost))
print(sorted(distance[end])[0] if distance[end] else '-1')


from collections import *
import sys
graph = defaultdict(list)
(N, E) = map(int, input().split())
for _ in range(E):
	(u, v, c) = map(int, input().split())
	graph[u].append((v, c))
	graph[v].append((u, c))
dq = deque()
(start, end) = map(int, input().split())
distance = [dict() for j in range(N + 1)]
dq.append((start, 0))
distance[start][0] = 0
while dq:
	(vertex, dist) = dq.popleft()
	for (k, v) in graph[vertex]:
		cost = v | dist
		if cost not in distance[k] and cost <= 1024:
			distance[k][cost] = 1
			dq.append((k, cost))
print(sorted(distance[end])[0] if distance[end] else '-1')


from collections import defaultdict, deque
from heapq import heappush, heappop
(n, m) = map(int, input().split())
graph = defaultdict(list)
for _ in range(m):
	(u, v, c) = map(int, input().split())
	graph[u].append([v, c])
	graph[v].append([u, c])
(a, b) = map(int, input().split())

def dfs(x, cost):
	visited = [[0] * 1024 for _ in range(1001)]
	visited[x][cost] = 1
	stack = [[x, cost]]
	while stack:
		(x, cost) = stack.pop()
		for (child, wt) in graph[x]:
			c_cost = cost | wt
			if not visited[child][c_cost]:
				visited[child][c_cost] = 1
				stack.append([child, c_cost])
	for i in range(1024):
		if visited[b][i] == 1:
			return i
	return -1
ans = dfs(a, 0)
print(ans)


from collections import defaultdict
from collections import deque
adj = defaultdict(list)
(N, E) = map(int, input().split())
for _ in range(E):
	(u, v, w) = map(int, input().split())
	adj[u].append((v, w))
	adj[v].append((u, w))
dq = deque()
(s, e) = map(int, input().split())
dist = [dict() for j in range(N + 1)]
dq.append((s, 0))
dist[s][0] = 0
while dq:
	(u, d) = dq.popleft()
	for (v, w) in adj[u]:
		cost = w | d
		if cost not in dist[v] and cost <= 1024:
			dist[v][cost] = 1
			dq.append((v, cost))
if dist[e]:
	print(sorted(dist[e])[0])
else:
	print(-1)


from collections import *
import sys
graph = defaultdict(list)
(N, E) = map(int, input().split())
for _ in range(E):
	(u, v, c) = map(int, input().split())
	graph[u].append((v, c))
	graph[v].append((u, c))
dq = deque()
(start, end) = map(int, input().split())
distance = [dict() for j in range(N + 1)]
dq.append((start, 0))
distance[start][0] = 0
while dq:
	(vertex, dist) = dq.popleft()
	for (k, v) in graph[vertex]:
		cost = v | dist
		if cost not in distance[k] and cost <= 1024:
			distance[k][cost] = 1
			dq.append((k, cost))
print(sorted(distance[end])[0] if distance[end] else '-1')


from collections import deque

def dfs(g, d, start):
	s = [(start, 0)]
	while s:
		(n, c) = s.pop()
		for (u, v) in g[n]:
			cc = c | v
			if not d[u][cc]:
				d[u][cc] = True
				s.append((u, cc))
(n, m) = map(int, input().strip().split())
g = [[] for _ in range(n)]
d = [[0 for _ in range(1024)] for _ in range(n)]
for _ in range(m):
	(u, v, c) = map(int, input().strip().split())
	u -= 1
	v -= 1
	g[u].append((v, c))
	g[v].append((u, c))
(a, b) = map(int, input().strip().split())
a -= 1
b -= 1
dfs(g, d, a)
result = -1
for i in range(1024):
	if d[b][i]:
		result = i
		break
print(result)


(n, e) = map(int, input().split())
graph = dict(((i, set()) for i in range(1, n + 1)))
costs = [[2000] * (n + 1) for i in range(0, n + 1)]
for _ in range(e):
	(a, b, w) = map(int, input().split())
	if w < costs[a][b]:
		costs[a][b] = w
		costs[b][a] = w
		graph[a].add(b)
		graph[b].add(a)
(start, end) = map(int, input().split())
cost_log = [set() for j in range(n + 1)]
queue = {(start, 0)}
while queue:
	(no, cost) = queue.pop()
	for ne in graph[no]:
		new_cost = costs[no][ne] | cost
		if new_cost not in cost_log[ne] and new_cost <= 1024:
			cost_log[ne].add(new_cost)
			queue.add((ne, new_cost))
print(sorted(cost_log[end])[0] if cost_log[end] else '-1')