





import math
import sys
class 							snake_case_		:







		def __init__(		self )					-> str:
				lowerCamelCase :			int    		=0
				lowerCamelCase :			str    		=[]
				lowerCamelCase :			Tuple    		={}  # To store the pos of node in array







		def       __lowercase (		self )					-> Dict:
				return self.cur_size == 0







		def       __lowercase (		self      ,  __lowercase )					-> Optional[Any]:
				lowerCamelCase :			Dict    		=self.left(__lowercase )
				lowerCamelCase :			Optional[Any]    		=self.right(__lowercase )
				if lc < self.cur_size and self.array(__lowercase )[0] < self.array(__lowercase )[0]:
						lowerCamelCase :			Optional[Any]    		=lc
				else:
						lowerCamelCase :			str    		=idx
				if rc < self.cur_size and self.array(__lowercase )[0] < self.array(__lowercase )[0]:
						lowerCamelCase :			Tuple    		=rc
				if smallest != idx:
						self.swap(__lowercase      ,  __lowercase )
						self.min_heapify(__lowercase )







		def       __lowercase (		self      ,  __lowercase )					-> Optional[Any]:
				# Inserts a node into the Priority Queue
				lowerCamelCase :			Optional[Any]    		=self.cur_size
				self.cur_size += 1
				self.array.append((sys.maxsize, tup[1]) )
				self.decrease_key((sys.maxsize, tup[1])      ,  tup[0] )







		def       __lowercase (		self )					-> List[Any]:
				# Removes and returns the min element at top of priority queue
				lowerCamelCase :			Union[str, Any]    		=self.array[0][1]
				lowerCamelCase :			List[str]    		=self.array[self.cur_size - 1]
				self.cur_size -= 1
				self.min_heapify(1 )
				del self.pos[min_node]
				return min_node







		def       __lowercase (		self      ,  __lowercase )					-> Optional[int]:
				# returns the index of left child
				return 2 * i + 1







		def       __lowercase (		self      ,  __lowercase )					-> Tuple:
				# returns the index of right child
				return 2 * i + 2







		def       __lowercase (		self      ,  __lowercase )					-> Optional[Any]:
				# returns the index of parent
				return math.floor(i / 2 )







		def       __lowercase (		self      ,  __lowercase      ,  __lowercase )					-> Dict:
				# swaps array elements at indices i and j
				# update the pos{}
				lowerCamelCase :			Dict    		=j
				lowerCamelCase :			int    		=i
				lowerCamelCase :			Optional[Any]    		=self.array[i]
				lowerCamelCase :			List[str]    		=self.array[j]
				lowerCamelCase :			int    		=temp







		def       __lowercase (		self      ,  __lowercase      ,  __lowercase )					-> int:
				lowerCamelCase :			Union[str, Any]    		=self.pos[tup[1]]
				# assuming the new_d is atmost old_d
				lowerCamelCase :			Dict    		=(new_d, tup[1])
				while idx > 0 and self.array[self.par(__lowercase )][0] > self.array[idx][0]:
						self.swap(__lowercase      ,  self.par(__lowercase ) )
						lowerCamelCase :			Optional[Any]    		=self.par(__lowercase )

class 							snake_case_		:







		def __init__(		self      ,  __lowercase )					-> Optional[Any]:
				lowerCamelCase :			Union[str, Any]    		={}  # To store graph: u -> (v,w)
				lowerCamelCase :			List[str]    		=num  # Number of nodes in graph
				# To store the distance from source vertex
				lowerCamelCase :			Any    		=[0] * self.num_nodes
				lowerCamelCase :			Optional[int]    		=[-1] * self.num_nodes  # To store the path







		def       __lowercase (		self      ,  __lowercase      ,  __lowercase      ,  __lowercase )					-> Tuple:
				#  Edge going from node u to v and v to u with weight w
				# u (w)-> v, v (w) -> u
				# Check if u already in graph
				if u in self.adjList:
						self.adjList[u].append((v, w) )
				else:
						lowerCamelCase :			Tuple    		=[(v, w)]

				# Assuming undirected graph
				if v in self.adjList:
						self.adjList[v].append((u, w) )
				else:
						lowerCamelCase :			Union[str, Any]    		=[(u, w)]







		def       __lowercase (		self )					-> int:
				# u -> v(w)
				for u in self.adjList:
						print(__lowercase      ,  '''->'''      ,  ''' -> '''.join(str(F"{v}({w})" ) for v, w in self.adjList[u] ) )







		def       __lowercase (		self      ,  __lowercase )					-> Optional[int]:
				# Flush old junk values in par[]
				lowerCamelCase :			Optional[int]    		=[-1] * self.num_nodes
				# src is the source node
				lowerCamelCase :			List[Any]    		=0
				lowerCamelCase :			Optional[int]    		=PriorityQueue()
				q.insert((0, src) )  # (dist from src, node)
				for u in self.adjList:
						if u != src:
								lowerCamelCase :			Optional[Any]    		=sys.maxsize  # Infinity
								lowerCamelCase :			Dict    		=-1

				while not q.is_empty():
						lowerCamelCase :			int    		=q.extract_min()  # Returns node with the min dist from source
						# Update the distance of all the neighbours of u and
						# if their prev dist was INFINITY then push them in Q
						for v, w in self.adjList[u]:
								lowerCamelCase :			Any    		=self.dist[u] + w
								if self.dist[v] > new_dist:
										if self.dist[v] == sys.maxsize:
												q.insert((new_dist, v) )
										else:
												q.decrease_key((self.dist[v], v)      ,  __lowercase )
										lowerCamelCase :			Any    		=new_dist
										lowerCamelCase :			List[Any]    		=u

        # Show the shortest distances from src
				self.show_distances(__lowercase )







		def       __lowercase (		self      ,  __lowercase )					-> Optional[int]:
				print(F"Distance from node: {src}" )
				for u in range(self.num_nodes ):
						print(F"Node {u} has distance: {self.dist[u]}" )







		def       __lowercase (		self      ,  __lowercase      ,  __lowercase )					-> List[str]:
				# To show the shortest path from src to dest
				# WARNING: Use it *after* calling dijkstra
				lowerCamelCase :			int    		=[]
				lowerCamelCase :			List[str]    		=0
				lowerCamelCase :			int    		=dest
				# Backtracking from dest to src
				while self.par[temp] != -1:
						path.append(__lowercase )
						if temp != src:
								for v, w in self.adjList[temp]:
										if v == self.par[temp]:
												cost += w
												break
						lowerCamelCase :			Tuple    		=self.par[temp]
				path.append(__lowercase )
				path.reverse()

				print(F"----Path to reach {dest} from {src}----" )
				for u in path:
						print(F"{u}"      ,  end=''' ''' )
						if u != dest:
								print('''-> '''      ,  end='''''' )

				print('''\nTotal cost of path: '''      ,  __lowercase )


if __name__ == "__main__":
				snake_case_				=      Graph(9)
				graph.add_edge(0, 1, 4)
				graph.add_edge(0, 7, 8)
				graph.add_edge(1, 2, 8)
				graph.add_edge(1, 7, 1_1)
				graph.add_edge(2, 3, 7)
				graph.add_edge(2, 8, 2)
				graph.add_edge(2, 5, 4)
				graph.add_edge(3, 4, 9)
				graph.add_edge(3, 5, 1_4)
				graph.add_edge(4, 5, 1_0)
				graph.add_edge(5, 6, 2)
				graph.add_edge(6, 7, 1)
				graph.add_edge(6, 8, 6)
				graph.add_edge(7, 8, 7)
				graph.show_graph()
				graph.dijkstra(0)
				graph.show_path(0, 4)

# OUTPUT
# 0 -> 1(4) -> 7(8)
# 1 -> 0(4) -> 2(8) -> 7(11)
# 7 -> 0(8) -> 1(11) -> 6(1) -> 8(7)
# 2 -> 1(8) -> 3(7) -> 8(2) -> 5(4)
# 3 -> 2(7) -> 4(9) -> 5(14)
# 8 -> 2(2) -> 6(6) -> 7(7)
# 5 -> 2(4) -> 3(14) -> 4(10) -> 6(2)
# 4 -> 3(9) -> 5(10)
# 6 -> 5(2) -> 7(1) -> 8(6)
# Distance from node: 0
# Node 0 has distance: 0
# Node 1 has distance: 4
# Node 2 has distance: 12
# Node 3 has distance: 19
# Node 4 has distance: 21
# Node 5 has distance: 11
# Node 6 has distance: 9
# Node 7 has distance: 8
# Node 8 has distance: 14
# ----Path to reach 4 from 0----
# 0 -> 7 -> 6 -> 5 -> 4
# Total cost of path:  21








def        A__						(							SCREAMING_SNAKE_CASE_ = 1_0_0_0		) ->  int:
		lowerCamelCase :			Dict    		=[]
		lowerCamelCase :			Dict    		=[]
		lowerCamelCase :			Union[str, Any]    		=3
		lowerCamelCase :			List[str]    		=5
		lowerCamelCase :			Union[str, Any]    		=1
		while True:
				lowerCamelCase :			Dict    		=z * temp
				if result < n:
						zmulti.append(SCREAMING_SNAKE_CASE_		)
						temp += 1
				else:
						lowerCamelCase :			List[Any]    		=1
						break
		while True:
				lowerCamelCase :			Optional[Any]    		=x * temp
				if result < n:
						xmulti.append(SCREAMING_SNAKE_CASE_		)
						temp += 1
				else:
						break
		lowerCamelCase :			str    		=list(set(xmulti + zmulti		)		)
		return sum(SCREAMING_SNAKE_CASE_		)


if __name__ == "__main__":
				print(F"""{solution() = }""")

