code: 
  
  
  """simple docstring"""
  
  
  
  
  import math
  import sys
  
  
  
  
  
  class __snake_case		:
  
  
  
  
  
  
  
     """simple docstring"""
  
  
  
  
     def __init__(		self							:Optional[int]       ):
            _a          =				0
            _a          =				[]
            _a          =				{}  # To store the pos of node in array
  
  
  
  
     def SCREAMING_SNAKE_CASE_      (		self							:Tuple       ):
            return self.cur_size == 0
  
  
  
  
     def SCREAMING_SNAKE_CASE_      (		self							:Union[str, Any]				,  UpperCamelCase__							:int       ):
            _a          =				self.left(__SCREAMING_SNAKE_CASE       )
            _a          =				self.right(__SCREAMING_SNAKE_CASE       )
            if lc < self.cur_size and self.array(__SCREAMING_SNAKE_CASE       )[0] < self.array(__SCREAMING_SNAKE_CASE       )[0]:
                   _a          =				lc
            else:
                   _a          =				idx
            if rc < self.cur_size and self.array(__SCREAMING_SNAKE_CASE       )[0] < self.array(__SCREAMING_SNAKE_CASE       )[0]:
                   _a          =				rc
            if smallest != idx:
                   self.swap(__SCREAMING_SNAKE_CASE				,  __SCREAMING_SNAKE_CASE       )
                   self.min_heapify(__SCREAMING_SNAKE_CASE       )
  
  
  
  
     def SCREAMING_SNAKE_CASE_      (		self							:Tuple				,  UpperCamelCase__							:List[Any]       ):
            _a          =				self.cur_size
            self.cur_size += 1
            self.array.append((sys.maxsize, tup[1])       )
            self.decrease_key((sys.maxsize, tup[1])				,  tup[0]       )
  
  
  
  
     def SCREAMING_SNAKE_CASE_      (		self							:List[Any]       ):
            _a          =				self.array[0][1]
            _a          =				self.array[self.cur_size - 1]
            self.cur_size -= 1
            self.min_heapify(1       )
            del self.pos[min_node]
            return min_node
  
  
  
  
     def SCREAMING_SNAKE_CASE_      (		self							:List[str]				,  UpperCamelCase__							:List[str]       ):
            return 2 * i + 1
  
  
  
  
     def SCREAMING_SNAKE_CASE_      (		self							:List[Any]				,  UpperCamelCase__							:Dict       ):
            return 2 * i + 2
  
  
  
  
     def SCREAMING_SNAKE_CASE_      (		self							:List[str]				,  UpperCamelCase__							:Optional[int]       ):
            return math.floor(i / 2       )
  
  
  
  
     def SCREAMING_SNAKE_CASE_      (		self							:int				,  UpperCamelCase__							:Union[str, Any]				,  UpperCamelCase__							:Dict       ):
            _a          =				j
            _a          =				i
            _a          =				self.array[i]
            _a          =				self.array[j]
            _a          =				temp
  
  
  
  
     def SCREAMING_SNAKE_CASE_      (		self							:Tuple				,  UpperCamelCase__							:Optional[Any]				,  UpperCamelCase__							:Tuple       ):
            _a          =				self.pos[tup[1]]
            # assuming the new_d is atmost old_d
            _a          =				(new_d, tup[1])
            while idx > 0 and self.array[self.par(__SCREAMING_SNAKE_CASE       )][0] > self.array[idx][0]:
                   self.swap(__SCREAMING_SNAKE_CASE				,  self.par(__SCREAMING_SNAKE_CASE       )       )
                   _a          =				self.par(__SCREAMING_SNAKE_CASE       )
  
  
  
  
  
  
  class __snake_case		:
  
  
  
  
  
  
  
     """simple docstring"""
  
  
  
  
     def __init__(		self							:List[str]				,  UpperCamelCase__							:int       ):
            _a          =				{}  # To store graph: u -> (v,w)
            _a          =				num  # Number of nodes in graph
            # To store the distance from source vertex
            _a          =				[0] * self.num_nodes
            _a          =				[-1] * self.num_nodes  # To store the path
  
  
  
  
     def SCREAMING_SNAKE_CASE_      (		self							:str				,  UpperCamelCase__							:List[str]				,  UpperCamelCase__							:Any				,  UpperCamelCase__							:List[str]       ):
  
            if u in self.adjList:
                   self.adjList[u].append((v, w)       )
            else:
                   _a          =				[(v, w)]
  
            # Assuming undirected graph
            if v in self.adjList:
                   self.adjList[v].append((u, w)       )
            else:
                   _a          =				[(u, w)]
  
  
  
  
     def SCREAMING_SNAKE_CASE_      (		self							:Optional[int]       ):
  
            for u in self.adjList:
                   print(__SCREAMING_SNAKE_CASE				,  "->"				,  " -> ".join(str(f'{v}({w})'       ) for v, w in self.adjList[u]       )       )
  
  
  
  
     def SCREAMING_SNAKE_CASE_      (		self							:Optional[Any]				,  UpperCamelCase__							:List[str]       ):
            _a          =				[-1] * self.num_nodes
            # src is the source node
            _a          =				0
            _a          =				PriorityQueue()
            q.insert((0, src)       )  # (dist from src, node)
            for u in self.adjList:
                   if u != src:
                          _a          =				sys.maxsize  # Infinity
                          _a          =				-1
  
            while not q.is_empty():
                   _a          =				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]:
                          _a          =				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)				,  __SCREAMING_SNAKE_CASE       )
                                 _a          =				new_dist
                                 _a          =				u
  
          # Show the shortest distances from src
            self.show_distances(__SCREAMING_SNAKE_CASE       )
  
  
  
  
     def SCREAMING_SNAKE_CASE_      (		self							:List[Any]				,  UpperCamelCase__							:str       ):
            print(f'Distance from node: {src}'       )
            for u in range(self.num_nodes       ):
                   print(f'Node {u} has distance: {self.dist[u]}'       )
  
  
  
  
     def SCREAMING_SNAKE_CASE_      (		self							:List[Any]				,  UpperCamelCase__							:List[Any]				,  UpperCamelCase__							:List[Any]       ):
            _a          =				[]
            _a          =				0
            _a          =				dest
            # Backtracking from dest to src
            while self.par[temp] != -1:
                   path.append(__SCREAMING_SNAKE_CASE       )
                   if temp != src:
                          for v, w in self.adjList[temp]:
                                 if v == self.par[temp]:
                                        cost += w
                                        break
                   _a          =				self.par[temp]
            path.append(__SCREAMING_SNAKE_CASE       )
            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: "				,  __SCREAMING_SNAKE_CASE       )
  
  
  if __name__ == "__main__":
     __SCREAMING_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, 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
  
style_context: 
  
  
  """simple docstring"""
  
  
  
  
  from __future__ import annotations
  
  __SCREAMING_SNAKE_CASE					=						[2, 1, 4, 5, 6, 0, 8, 9, 1, 2, 0, 6, 4, 2, 0, 6, 5, 3, 2, 7]
  
  
  
  
  
  class __snake_case		:
  
  
  
  
  
  
  
     """simple docstring"""
  
  
  
  
     def __init__(		self							:Optional[Any]				,  UpperCamelCase__							:int       ):
            _a          =				-1
            _a          =				-1
            _a          =				[-1] * length
            _a          =				None
            _a          =				None
  
  
  
  
     def __repr__(		self							:Optional[Any]       ):
            return f'Node(min_value={self.minn} max_value={self.maxx})'
  
  
  
  
  
  
  def 						__a      (  a					):
  
  
  
  
  
         """simple docstring"""
  
  
  
  
  
  
  
         _a          =				Node(len(a					)					)
         _a   , _a          =				min(a					), max(a					)
         # Leaf node case where the node contains only one unique value
         if root.minn == root.maxx:
                return root
         _a          =				(root.minn + root.maxx) // 2
  
         _a          =				[]
         _a          =				[]
  
         for index, num in enumerate(a					):
                if num <= pivot:
                       left_arr.append(a					)
                else:
                       right_arr.append(a					)
                _a          =				len(a					)
         _a          =				build_tree(a					)
         _a          =				build_tree(a					)
         return root
  
  
  
  def 						__a      (  a,		a,		a					):
  
  
  
  
  
         """simple docstring"""
  
  
  
  
  
  
  
         if index < 0 or node is None:
                return 0
         # Leaf node cases
         if node.minn == node.maxx:
                return index + 1 if node.minn == num else 0
         _a          =				(node.minn + node.maxx) // 2
         if num <= pivot:
                # go the left subtree and map index to the left subtree
                return rank_till_index(node.left,		a,		node.map_left[index] - 1					)
         else:
                # go to the right subtree and map index to the right subtree
                return rank_till_index(node.right,		a,		index - node.map_left[index]					)
  
  
  
  def 						__a      (  a,		a,		a,		a					):
  
  
  
  
  
         """simple docstring"""
  
  
  
  
  
  
  
         if start > end:
                return 0
         _a          =				rank_till_index(a,		a,		a					)
         _a          =				rank_till_index(a,		a,		start - 1					)
         return rank_till_end - rank_before_start
  
  
  
  def 						__a      (  a,		a,		a,		a					):
  
  
  
  
  
         """simple docstring"""
  
  
  
  
  
  
  
         if index > (end - start) or start > end or node is None:
                return -1
         # Leaf node case
         if node.minn == node.maxx:
                return node.minn
         # Number of elements in the left subtree in interval [start, end]
         _a          =				node.map_left[end] - (
             node.map_left[start - 1] if start else 0
         )
         if num_elements_in_left_tree > index:
                return quantile(
                    node.left,		a,		(node.map_left[start - 1] if start else 0),		node.map_left[end] - 1,		)
         else:
                return quantile(
                    node.right,		index - num_elements_in_left_tree,		start - (node.map_left[start - 1] if start else 0),		end - node.map_left[end],		)
  
  
  
  def 						__a      (  a,		a,		a,		a,		a					):
  
  
  
  
  
         """simple docstring"""
  
  
  
  
  
  
  
         if (
             start > end
             or node is None
             or start_num > end_num
             or node.minn > end_num
             or node.maxx < start_num
         ):
                return 0
         if start_num <= node.minn and node.maxx <= end_num:
                return end - start + 1
         _a          =				range_counting(
             node.left,		(node.map_left[start - 1] if start else 0),		node.map_left[end] - 1,		a,		a,		)
         _a          =				range_counting(
             node.right,		start - (node.map_left[start - 1] if start else 0),		end - node.map_left[end],		a,		a,		)
         return left + right
  
  
  if __name__ == "__main__":
     import doctest
  
     doctest.testmod()
  