


from __future__ import annotations


def   a						(				SCREAMING_SNAKE_CASE_   :		Optional[int]							):






       """simple docstring"""





       assert (
           isinstance(snake_case__				,      snake_case__							) and mask > 0
       ), F"""mask needs to be positive integer, your input {mask}"""
       UpperCamelCase     :						Union[str, Any] 						=		[]
       UpperCamelCase     :						int 						=		mask

       while submask:
              all_submasks.append(snake_case__							)
              UpperCamelCase     :						Union[str, Any] 						=		(submask - 1) & mask

       return all_submasks


if __name__ == "__main__":
  import doctest

  doctest.testmod()









import math
import sys



class  __UpperCAmelCase						:







			def __init__(      self:    str	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    0
									_SCREAMING_SNAKE_CASE       =    []
									_SCREAMING_SNAKE_CASE       =    {}  # To store the pos of node in array







			def 				UpperCamelCase (      self:    List[str]	):







									'''simple docstring'''




									return self.cur_size == 0







			def 				UpperCamelCase (      self:    int ,      UpperCAmelCase_:    Union[str, Any]	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    self.left(UpperCAmelCase_	)
									_SCREAMING_SNAKE_CASE       =    self.right(UpperCAmelCase_	)
									if lc < self.cur_size and self.array(UpperCAmelCase_	)[0] < self.array(UpperCAmelCase_	)[0]:
															_SCREAMING_SNAKE_CASE       =    lc
									else:
															_SCREAMING_SNAKE_CASE       =    idx
									if rc < self.cur_size and self.array(UpperCAmelCase_	)[0] < self.array(UpperCAmelCase_	)[0]:
															_SCREAMING_SNAKE_CASE       =    rc
									if smallest != idx:
															self.swap(UpperCAmelCase_ ,      UpperCAmelCase_	)
															self.min_heapify(UpperCAmelCase_	)







			def 				UpperCamelCase (      self:    int ,      UpperCAmelCase_:    Tuple	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    self.cur_size
									self.cur_size += 1
									self.array.append((sys.maxsize, tup[1])	)
									self.decrease_key((sys.maxsize, tup[1]) ,      tup[0]	)







			def 				UpperCamelCase (      self:    Union[str, Any]	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    self.array[0][1]
									_SCREAMING_SNAKE_CASE       =    self.array[self.cur_size - 1]
									self.cur_size -= 1
									self.min_heapify(1	)
									del self.pos[min_node]
									return min_node







			def 				UpperCamelCase (      self:    Dict ,      UpperCAmelCase_:    List[Any]	):







									'''simple docstring'''




									return 2 * i + 1







			def 				UpperCamelCase (      self:    Optional[Any] ,      UpperCAmelCase_:    List[Any]	):







									'''simple docstring'''




									return 2 * i + 2







			def 				UpperCamelCase (      self:    Union[str, Any] ,      UpperCAmelCase_:    int	):







									'''simple docstring'''




									return math.floor(i / 2	)







			def 				UpperCamelCase (      self:    str ,      UpperCAmelCase_:    Optional[Any] ,      UpperCAmelCase_:    str	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    j
									_SCREAMING_SNAKE_CASE       =    i
									_SCREAMING_SNAKE_CASE       =    self.array[i]
									_SCREAMING_SNAKE_CASE       =    self.array[j]
									_SCREAMING_SNAKE_CASE       =    temp







			def 				UpperCamelCase (      self:    int ,      UpperCAmelCase_:    Dict ,      UpperCAmelCase_:    Dict	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    self.pos[tup[1]]
									# assuming the new_d is atmost old_d
									_SCREAMING_SNAKE_CASE       =    (new_d, tup[1])
									while idx > 0 and self.array[self.par(UpperCAmelCase_	)][0] > self.array[idx][0]:
															self.swap(UpperCAmelCase_ ,      self.par(UpperCAmelCase_	)	)
															_SCREAMING_SNAKE_CASE       =    self.par(UpperCAmelCase_	)



class  __UpperCAmelCase						:







			def __init__(      self:    Tuple ,      UpperCAmelCase_:    Any	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    {}  # To store graph: u -> (v,w)
									_SCREAMING_SNAKE_CASE       =    num  # Number of nodes in graph
									# To store the distance from source vertex
									_SCREAMING_SNAKE_CASE       =    [0] * self.num_nodes
									_SCREAMING_SNAKE_CASE       =    [-1] * self.num_nodes  # To store the path







			def 				UpperCamelCase (      self:    Tuple ,      UpperCAmelCase_:    int ,      UpperCAmelCase_:    List[Any] ,      UpperCAmelCase_:    Any	):







									'''simple docstring'''




									if u in self.adjList:
															self.adjList[u].append((v, w)	)
									else:
															_SCREAMING_SNAKE_CASE       =    [(v, w)]

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







			def 				UpperCamelCase (      self:    Dict	):







									'''simple docstring'''




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







			def 				UpperCamelCase (      self:    Optional[int] ,      UpperCAmelCase_:    str	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    [-1] * self.num_nodes
									# src is the source node
									_SCREAMING_SNAKE_CASE       =    0
									_SCREAMING_SNAKE_CASE       =    PriorityQueue()
									q.insert((0, src)	)  # (dist from src, node)
									for u in self.adjList:
															if u != src:
																					_SCREAMING_SNAKE_CASE       =    sys.maxsize  # Infinity
																					_SCREAMING_SNAKE_CASE       =    -1

									while not q.is_empty():
															_SCREAMING_SNAKE_CASE       =    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]:
																					_SCREAMING_SNAKE_CASE       =    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) ,      UpperCAmelCase_	)
																											_SCREAMING_SNAKE_CASE       =    new_dist
																											_SCREAMING_SNAKE_CASE       =    u

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







			def 				UpperCamelCase (      self:    Optional[int] ,      UpperCAmelCase_:    int	):







									'''simple docstring'''




									print(F'Distance from node: {src}'	)
									for u in range(self.num_nodes	):
															print(F'Node {u} has distance: {self.dist[u]}'	)







			def 				UpperCamelCase (      self:    str ,      UpperCAmelCase_:    str ,      UpperCAmelCase_:    List[str]	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    []
									_SCREAMING_SNAKE_CASE       =    0
									_SCREAMING_SNAKE_CASE       =    dest
									# Backtracking from dest to src
									while self.par[temp] != -1:
															path.append(UpperCAmelCase_	)
															if temp != src:
																					for v, w in self.adjList[temp]:
																											if v == self.par[temp]:
																																	cost += w
																																	break
															_SCREAMING_SNAKE_CASE       =    self.par[temp]
									path.append(UpperCAmelCase_	)
									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: """ ,      UpperCAmelCase_	)


if __name__ == "__main__":
		UpperCamelCase												=      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, 11)
		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, 14)
		graph.add_edge(4, 5, 10)
		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

