






'''simple docstring'''







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




class   __SCREAMING_SNAKE_CASE       :


  """simple docstring"""


  def __init__(			self   ,	UpperCamelCase__	):






         """simple docstring"""


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







  def __lt__(			self   ,	UpperCamelCase__	):






         """simple docstring"""


         return self.key < other.key







  def __repr__(			self	):






         """simple docstring"""


         return self.id







  def    _a       (			self   ,	UpperCamelCase__	):






         """simple docstring"""


         self.neighbors.append(UpperCamelCase__	)







  def    _a       (			self   ,	UpperCamelCase__   ,	UpperCamelCase__	):






         """simple docstring"""


         a_						     =			weight





def       __UpperCamelCase					(      lowercase_       :  Optional[int]   ,       lowercase_       :  Dict   ,       lowercase_       :  List[str]   ,       lowercase_       :  Optional[Any]   ):
       """simple docstring"""




       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]   ,       lowercase_   )
       graph[b - 1].add_edge(graph[a - 1]   ,       lowercase_   )


def       __UpperCamelCase					(      lowercase_       :  list   ,       lowercase_       :  Vertex   ):
       """simple docstring"""




       a_						     =			[]
       for u in graph:
              a_						     =			math.inf
              a_						     =			None
       a_						     =			0
       a_						     =			graph[:]
       while q:
              a_						     =			min(lowercase_   )
              q.remove(lowercase_   )
              for v in u.neighbors:
                     if (v in q) and (u.edges[v.id] < v.key):
                            a_						     =			u
                            a_						     =			u.edges[v.id]
       for i in range(1   ,       len(lowercase_   )   ):
              a.append((int(graph[i].id   ) + 1, int(graph[i].pi.id   ) + 1)   )
       return a


def       __UpperCamelCase					(      lowercase_       :  list   ,       lowercase_       :  Vertex   ):
       """simple docstring"""




       for u in graph:
              a_						     =			math.inf
              a_						     =			None
       a_						     =			0

       a_						     =			list(lowercase_   )
       hq.heapify(lowercase_   )

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

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


def       __UpperCamelCase					(      ):
       """simple docstring"""






if __name__ == "__main__":
  import doctest

  doctest.testmod()












'''simple docstring'''







from __future__ import annotations

from collections.abc import Iterator
from typing import Generic, TypeVar

__lowerCAmelCase        =							TypeVar("T")




class   __SCREAMING_SNAKE_CASE       (Generic[T]       ):


  """simple docstring"""


  def __init__(			self   ,	UpperCamelCase__	):






         """simple docstring"""


         a_						     =			data
         a_						     =			None







  def __str__(			self	):






         """simple docstring"""


         return f'{self.data}'





class   __SCREAMING_SNAKE_CASE       (Generic[T]       ):


  """simple docstring"""


  def __init__(			self	):






         """simple docstring"""


         a_						     =			None







  def __iter__(			self	):






         """simple docstring"""


         a_						     =			self.top
         while node:
                yield node.data
                a_						     =			node.next







  def __str__(			self	):






         """simple docstring"""


         return "->".join([str(UpperCamelCase__	) for item in self]	)







  def __len__(			self	):






         """simple docstring"""


         return len(tuple(iter(self	)	)	)







  def    _a       (			self	):






         """simple docstring"""


         return self.top is None







  def    _a       (			self   ,	UpperCamelCase__	):






         """simple docstring"""


         a_						     =			Node(UpperCamelCase__	)
         if not self.is_empty():
                a_						     =			self.top
         a_						     =			node







  def    _a       (			self	):






         """simple docstring"""


         if self.is_empty():
                raise IndexError('pop from empty stack'	)
         assert isinstance(self.top   ,	UpperCamelCase__	)
         a_						     =			self.top
         a_						     =			self.top.next
         return pop_node.data







  def    _a       (			self	):






         """simple docstring"""


         if self.is_empty():
                raise IndexError('peek from empty stack'	)

         assert self.top is not None
         return self.top.data







  def    _a       (			self	):






         """simple docstring"""


         a_						     =			None


if __name__ == "__main__":
  from doctest import testmod

  testmod()




