






import heapq as hq
import math
from collections.abc import Iterator




class     _lowerCAmelCase:





       """simple docstring"""







       def __init__( self  ,      _lowerCamelCase							):
         UpperCamelCase_: Dict   				=    str(id_							)
         UpperCamelCase_: Union[str, Any]   				=    None
         UpperCamelCase_: Tuple   				=    None
         UpperCamelCase_: int   				=    []
         UpperCamelCase_: Dict   				=    {}  # {vertex:distance}





       def __lt__( self  ,      _lowerCamelCase							):
         return self.key < other.key





       def __repr__( self							):
         return self.id





       def       _a   ( self  ,      _lowerCamelCase							):
         self.neighbors.append(_lowerCamelCase							)





       def       _a   ( self  ,      _lowerCamelCase  ,      _lowerCamelCase							):
         UpperCamelCase_: Any   				=    weight







def   snake_case (UpperCAmelCase__     ,   UpperCAmelCase__     ,   UpperCAmelCase__     ,   UpperCAmelCase__  )	->    Tuple:
  # 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]     ,   UpperCAmelCase__  )
  graph[b - 1].add_edge(graph[a - 1]     ,   UpperCAmelCase__  )

def   snake_case (UpperCAmelCase__     ,   UpperCAmelCase__  )	->    list:
  UpperCamelCase_: Optional[int]   				=    []
  for u in graph:
    UpperCamelCase_: str   				=    math.inf
    UpperCamelCase_: Dict   				=    None
  UpperCamelCase_: Union[str, Any]   				=    0
  UpperCamelCase_: List[Any]   				=    graph[:]
  while q:
    UpperCamelCase_: Tuple   				=    min(UpperCAmelCase__  )
    q.remove(UpperCAmelCase__  )
    for v in u.neighbors:
      if (v in q) and (u.edges[v.id] < v.key):
        UpperCamelCase_: int   				=    u
        UpperCamelCase_: Any   				=    u.edges[v.id]
  for i in range(1     ,   len(UpperCAmelCase__  )  ):
    a.append((int(graph[i].id  ) + 1, int(graph[i].pi.id  ) + 1)  )
  return a

def   snake_case (UpperCAmelCase__     ,   UpperCAmelCase__  )	->    Iterator[tuple]:
  for u in graph:
    UpperCamelCase_: Optional[int]   				=    math.inf
    UpperCamelCase_: Union[str, Any]   				=    None
  UpperCamelCase_: Optional[Any]   				=    0

  UpperCamelCase_: Optional[int]   				=    list(UpperCAmelCase__  )
  hq.heapify(UpperCAmelCase__  )

  while h:
    UpperCamelCase_: Optional[Any]   				=    hq.heappop(UpperCAmelCase__  )
    for v in u.neighbors:
      if (v in h) and (u.edges[v.id] < v.key):
        UpperCamelCase_: str   				=    u
        UpperCamelCase_: Dict   				=    u.edges[v.id]
        hq.heapify(UpperCAmelCase__  )

  for i in range(1     ,   len(UpperCAmelCase__  )  ):
    yield (int(graph[i].id  ) + 1, int(graph[i].pi.id  ) + 1)

def   snake_case ()	->    None:
  pass


if __name__ == "__main__":
   import doctest

   doctest.testmod()







import os


# All paths are set with the intent you should run this script from the root of the repo with the command
# python utils/check_doctest_list.py
A_		:		List[str]		     =			'.'


if __name__ == "__main__":
   A_		:		Dict		     =			os.path.join(REPO_PATH, 'utils/documentation_tests.txt')
   A_		:		Dict		     =			[]
   A_		:		Optional[Any]		     =			[]
   with open(doctest_file_path) as fp:
      for line in fp:
         A_		:		Tuple		     =			line.strip()
         A_		:		Any		     =			os.path.join(REPO_PATH, line)
         if not (os.path.isfile(path) or os.path.isdir(path)):
            non_existent_paths.append(line)
         all_paths.append(path)
   if len(non_existent_paths) > 0:
      A_		:		str		     =			'\n'.join(non_existent_paths)
      raise ValueError(F'''`utils/documentation_tests.txt` contains non-existent paths:\n{non_existent_paths}''')
   if all_paths != sorted(all_paths):
      raise ValueError('Files in `utils/documentation_tests.txt` are not in alphabetical order.')