



"""simple docstring"""





import heapq as hq
import math
from collections.abc import Iterator
class    lowercase__     :







       '''simple docstring'''


       def __init__(							self    :						Dict	,       _UpperCAmelCase    :						Optional[int]					)				->		Optional[Any]:


             '''simple docstring'''




             UpperCAmelCase_    				=							str(id_					)
             UpperCAmelCase_    				=							None
             UpperCAmelCase_    				=							None
             UpperCAmelCase_    				=							[]
             UpperCAmelCase_    				=							{}  # {vertex:distance}



       def __lt__(							self    :						str	,       _UpperCAmelCase    :						Optional[Any]					)				->		List[str]:


             '''simple docstring'''




             return self.key < other.key



       def __repr__(							self    :						Tuple					)				->		Optional[int]:


             '''simple docstring'''




             return self.id



       def   lowercase__       (							self    :						Dict	,       _UpperCAmelCase    :						List[str]					)				->		Optional[int]:


             '''simple docstring'''




             self.neighbors.append(_UpperCAmelCase					)







       def   lowercase__       (							self    :						Tuple	,       _UpperCAmelCase    :						Any	,       _UpperCAmelCase    :						str					)				->		Any:


             '''simple docstring'''




             UpperCAmelCase_    				=							weight



def      a__			(   lowerCAmelCase__			,    lowerCAmelCase__			,    lowerCAmelCase__			,    lowerCAmelCase__   ):
      # add the neighbors:
      graph[a - 1].add_neighbor(graph[b - 1]   )
      graph[b - 1].add_neighbor(graph[a - 1]   )
      # add the edges:
      graph[a - 1].add_edge(graph[b - 1]			,    lowerCAmelCase__   )
      graph[b - 1].add_edge(graph[a - 1]			,    lowerCAmelCase__   )
def      a__			(   lowerCAmelCase__			,    lowerCAmelCase__   ):
      UpperCAmelCase_    				=							[]
      for u in graph:
            UpperCAmelCase_    				=							math.inf
            UpperCAmelCase_    				=							None
      UpperCAmelCase_    				=							0
      UpperCAmelCase_    				=							graph[:]
      while q:
            UpperCAmelCase_    				=							min(lowerCAmelCase__   )
            q.remove(lowerCAmelCase__   )
            for v in u.neighbors:
                  if (v in q) and (u.edges[v.id] < v.key):
                        UpperCAmelCase_    				=							u
                        UpperCAmelCase_    				=							u.edges[v.id]
      for i in range(1			,    len(lowerCAmelCase__   )   ):
            a.append((int(graph[i].id   ) + 1, int(graph[i].pi.id   ) + 1)   )
      return a
def      a__			(   lowerCAmelCase__			,    lowerCAmelCase__   ):
      for u in graph:
            UpperCAmelCase_    				=							math.inf
            UpperCAmelCase_    				=							None
      UpperCAmelCase_    				=							0

      UpperCAmelCase_    				=							list(lowerCAmelCase__   )
      hq.heapify(lowerCAmelCase__   )

      while h:
            UpperCAmelCase_    				=							hq.heappop(lowerCAmelCase__   )
            for v in u.neighbors:
                  if (v in h) and (u.edges[v.id] < v.key):
                        UpperCAmelCase_    				=							u
                        UpperCAmelCase_    				=							u.edges[v.id]
                        hq.heapify(lowerCAmelCase__   )

      for i in range(1			,    len(lowerCAmelCase__   )   ):
            yield (int(graph[i].id   ) + 1, int(graph[i].pi.id   ) + 1)
def      a__			(   ):
      pass


if __name__ == "__main__":
  import doctest

  doctest.testmod()









"""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()




