



"""simple docstring"""





from __future__ import annotations

from sys import maxsize
from typing import Generic, TypeVar

lowerCamelCase      =   TypeVar("""T""")
def      a__			(   lowerCAmelCase__   ):
      return (position - 1) // 2
def      a__			(   lowerCAmelCase__   ):
      return (2 * position) + 1
def      a__			(   lowerCAmelCase__   ):
      return (2 * position) + 2
class    lowercase__     (					Generic[T]   ):







       '''simple docstring'''


       def __init__(							self    :						int					)				->		None:


             '''simple docstring'''




             UpperCAmelCase_    				=							[]
             UpperCAmelCase_    				=							{}
             UpperCAmelCase_    				=							0



       def __len__(							self    :						Optional[int]					)				->		int:


             '''simple docstring'''




             return self.elements



       def __repr__(							self    :						str					)				->		str:


             '''simple docstring'''




             return str(self.heap					)



       def   lowercase__       (							self    :						Optional[Any]					)				->		bool:


             '''simple docstring'''




             return self.elements == 0



       def   lowercase__       (							self    :						List[str]	,       _UpperCAmelCase    :						T	,       _UpperCAmelCase    :						int					)				->		None:


             '''simple docstring'''




             self.heap.append((elem, weight)					)
             UpperCAmelCase_    				=							self.elements
             self.elements += 1
             self._bubble_up(_UpperCAmelCase					)



       def   lowercase__       (							self    :						int					)				->		T:


             '''simple docstring'''




             if self.elements > 1:
                   self._swap_nodes(0	,       self.elements - 1					)
             UpperCAmelCase_				,					UpperCAmelCase_    				=							self.heap.pop()
             del self.position_map[elem]
             self.elements -= 1
             if self.elements > 0:
                   UpperCAmelCase_				,					UpperCAmelCase_    				=							self.heap[0]
                   self._bubble_down(_UpperCAmelCase					)
             return elem



       def   lowercase__       (							self    :						Dict	,       _UpperCAmelCase    :						T	,       _UpperCAmelCase    :						int					)				->		None:


             '''simple docstring'''




             UpperCAmelCase_    				=							self.position_map[elem]
             UpperCAmelCase_    				=							(elem, weight)
             if position > 0:
                   UpperCAmelCase_    				=							get_parent_position(_UpperCAmelCase					)
                   UpperCAmelCase_				,					UpperCAmelCase_    				=							self.heap[parent_position]
                   if parent_weight > weight:
                         self._bubble_up(_UpperCAmelCase					)
                   else:
                         self._bubble_down(_UpperCAmelCase					)
             else:
                   self._bubble_down(_UpperCAmelCase					)



       def   lowercase__       (							self    :						Union[str, Any]	,       _UpperCAmelCase    :						T					)				->		None:


             '''simple docstring'''




             UpperCAmelCase_    				=							self.position_map[elem]
             if curr_pos == 0:
                   return None
             UpperCAmelCase_    				=							get_parent_position(_UpperCAmelCase					)
             UpperCAmelCase_				,					UpperCAmelCase_    				=							self.heap[curr_pos]
             UpperCAmelCase_				,					UpperCAmelCase_    				=							self.heap[parent_position]
             if parent_weight > weight:
                   self._swap_nodes(_UpperCAmelCase	,       _UpperCAmelCase					)
                   return self._bubble_up(_UpperCAmelCase					)
             return None



       def   lowercase__       (							self    :						Any	,       _UpperCAmelCase    :						T					)				->		None:


             '''simple docstring'''




             UpperCAmelCase_    				=							self.position_map[elem]
             UpperCAmelCase_				,					UpperCAmelCase_    				=							self.heap[curr_pos]
             UpperCAmelCase_    				=							get_child_left_position(_UpperCAmelCase					)
             UpperCAmelCase_    				=							get_child_right_position(_UpperCAmelCase					)
             if child_left_position < self.elements and child_right_position < self.elements:
                   UpperCAmelCase_				,					UpperCAmelCase_    				=							self.heap[child_left_position]
                   UpperCAmelCase_				,					UpperCAmelCase_    				=							self.heap[child_right_position]
                   if child_right_weight < child_left_weight and child_right_weight < weight:
                         self._swap_nodes(_UpperCAmelCase	,       _UpperCAmelCase					)
                         return self._bubble_down(_UpperCAmelCase					)
             if child_left_position < self.elements:
                   UpperCAmelCase_				,					UpperCAmelCase_    				=							self.heap[child_left_position]
                   if child_left_weight < weight:
                         self._swap_nodes(_UpperCAmelCase	,       _UpperCAmelCase					)
                         return self._bubble_down(_UpperCAmelCase					)
             else:
                   return None
             if child_right_position < self.elements:
                   UpperCAmelCase_				,					UpperCAmelCase_    				=							self.heap[child_right_position]
                   if child_right_weight < weight:
                         self._swap_nodes(_UpperCAmelCase	,       _UpperCAmelCase					)
                         return self._bubble_down(_UpperCAmelCase					)
             return None







       def   lowercase__       (							self    :						Tuple	,       _UpperCAmelCase    :						int	,       _UpperCAmelCase    :						int					)				->		None:


             '''simple docstring'''




             UpperCAmelCase_    				=							self.heap[nodea_pos][0]
             UpperCAmelCase_    				=							self.heap[nodea_pos][0]
             UpperCAmelCase_				,					UpperCAmelCase_    				=							(
                 self.heap[nodea_pos],
                 self.heap[nodea_pos],
             )
             UpperCAmelCase_    				=							nodea_pos
             UpperCAmelCase_    				=							nodea_pos



class    lowercase__     (					Generic[T]   ):







       '''simple docstring'''


       def __init__(							self    :						Any					)				->		None:


             '''simple docstring'''




             UpperCAmelCase_    				=							{}
             UpperCAmelCase_    				=							0



       def __repr__(							self    :						List[str]					)				->		str:


             '''simple docstring'''




             return str(self.connections					)



       def __len__(							self    :						Optional[Any]					)				->		int:


             '''simple docstring'''




             return self.nodes



       def   lowercase__       (							self    :						int	,       _UpperCAmelCase    :						T					)				->		None:


             '''simple docstring'''




             if node not in self.connections:
                   UpperCAmelCase_    				=							{}
                   self.nodes += 1







       def   lowercase__       (							self    :						int	,       _UpperCAmelCase    :						T	,       _UpperCAmelCase    :						T	,       _UpperCAmelCase    :						int					)				->		None:


             '''simple docstring'''




             self.add_node(_UpperCAmelCase					)
             self.add_node(_UpperCAmelCase					)
             UpperCAmelCase_    				=							weight
             UpperCAmelCase_    				=							weight



def      a__			(   lowerCAmelCase__			,    ):
      UpperCAmelCase_    				=							{node: maxsize for node in graph.connections}
      UpperCAmelCase_    				=							{node: None for node in graph.connections}

      UpperCAmelCase_    				=							MinPriorityQueue()
      for node, weight in dist.items():
            priority_queue.push(lowerCAmelCase__			,    lowerCAmelCase__   )

      if priority_queue.is_empty():
            return dist, parent

      # initialization
      UpperCAmelCase_    				=							priority_queue.extract_min()
      UpperCAmelCase_    				=							0
      for neighbour in graph.connections[node]:
            if dist[neighbour] > dist[node] + graph.connections[node][neighbour]:
                  UpperCAmelCase_    				=							dist[node] + graph.connections[node][neighbour]
                  priority_queue.update_key(lowerCAmelCase__			,    dist[neighbour]   )
                  UpperCAmelCase_    				=							node

    # running prim's algorithm
      while not priority_queue.is_empty():
            UpperCAmelCase_    				=							priority_queue.extract_min()
            for neighbour in graph.connections[node]:
                  if dist[neighbour] > dist[node] + graph.connections[node][neighbour]:
                        UpperCAmelCase_    				=							dist[node] + graph.connections[node][neighbour]
                        priority_queue.update_key(lowerCAmelCase__			,    dist[neighbour]   )
                        UpperCAmelCase_    				=							node
      return dist, parent









"""simple docstring"""





lowerCamelCase      =		{
    "joule": 1.0,
    "kilojoule": 1_000,
    "megajoule": 1_000_000,
    "gigajoule": 1_000_000_000,
    "wattsecond": 1.0,
    "watthour": 3_600,
    "kilowatthour": 3_600_000,
    "newtonmeter": 1.0,
    "calorie_nutr": 4_186.8,
    "kilocalorie_nutr": 4_186_800.00,
    "electronvolt": 1.6_0_2_1_7_6_6_3_4e-1_9,
    "britishthermalunit_it": 1_055.05_585,
    "footpound": 1.355_818,
}
def      a__			(   lowerCAmelCase__			,    lowerCAmelCase__			,    lowerCAmelCase__   ):
      if to_type not in ENERGY_CONVERSION or from_type not in ENERGY_CONVERSION:
            UpperCAmelCase_    				=							(
                f"""Incorrect 'from_type' or 'to_type' value: {from_type!r}, {to_type!r}\n"""
                f"""Valid values are: {', '.join(lowerCAmelCase__   )}"""
            )
            raise ValueError(lowerCAmelCase__   )
      return value * ENERGY_CONVERSION[from_type] / ENERGY_CONVERSION[to_type]


if __name__ == "__main__":
  import doctest

  doctest.testmod()




