


from __future__ import annotations




class 							lowerCamelCase   :


	def __init__(    self				,     lowercase__=None):
							__UpperCAmelCase			:							List[Any]	    =	data
							__UpperCAmelCase			:							Optional[int]	    =	None


	def __repr__(    self):
							__UpperCAmelCase			:							Dict	    =	[]
							__UpperCAmelCase			:							int	    =	self
							while temp:
													string_rep.append(F"{temp.data}")
													__UpperCAmelCase			:							Union[str, Any]	    =	temp.next
							return "->".join(lowercase__)






def     __SCREAMING_SNAKE_CASE							(       lowercase_      )		->     int:




						'''simple docstring'''







						if not elements_list:
												raise Exception('''The Elements List is empty'''      )

						__UpperCAmelCase			:							List[Any]	    =	Node(elements_list[0]      )
						for i in range(1      ,       len(a__      )      ):
												__UpperCAmelCase			:							str	    =	Node(elements_list[i]      )
												__UpperCAmelCase			:							Tuple	    =	current.next
						return head




def     __SCREAMING_SNAKE_CASE							(       lowercase_      )		->     List[str]:




						'''simple docstring'''







						if head_node is not None and isinstance(a__      ,       a__      ):
												print_reverse(head_node.next      )
												print(head_node.data      )




def     __SCREAMING_SNAKE_CASE							(       )		->     Optional[int]:




						'''simple docstring'''







						from doctest import testmod

						testmod()

						__UpperCAmelCase			:							int	    =	make_linked_list([14, 52, 14, 12, 43]      )
						print('''Linked List:'''      )
						print(a__      )
						print('''Elements in Reverse:'''      )
						print_reverse(a__      )


if __name__ == "__main__":
				main()









"""simple docstring"""


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




class 						__UpperCamelCase     :
					def __init__(							self							:	Union[str, Any]     , UpperCAmelCase							:	List[Any]   )	->       List[str]:
											lowerCAmelCase   :Dict						=			str(id_   )
											lowerCAmelCase   :str						=			None
											lowerCAmelCase   :Any						=			None
											lowerCAmelCase   :List[str]						=			[]
											lowerCAmelCase   :List[Any]						=			{}  # {vertex:distance}
					def __lt__(							self							:	Union[str, Any]     , UpperCAmelCase							:	Any   )	->       str:
											return self.key < other.key
					def __repr__(							self							:	Union[str, Any]   )	->       Dict:
											return self.id
					def        UpperCAmelCase__ (							self							:	Any     , UpperCAmelCase							:	Tuple   )	->       List[str]:
											self.neighbors.append(UpperCAmelCase   )
					def        UpperCAmelCase__ (							self							:	str     , UpperCAmelCase							:	Optional[Any]     , UpperCAmelCase							:	List[Any]   )	->       Optional[int]:
											lowerCAmelCase   :str						=			weight


def        UpperCAmelCase      (					a__     ,      a__     ,      a__     ,      a__ ):





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


def        UpperCAmelCase      (					a__     ,      a__ ):





						'''simple docstring'''






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


def        UpperCAmelCase      (					a__     ,      a__ ):





						'''simple docstring'''






						for u in graph:
												lowerCAmelCase   :List[str]						=			math.inf
												lowerCAmelCase   :str						=			None
						lowerCAmelCase   :Optional[int]						=			0

						lowerCAmelCase   :Dict						=			list(a__ )
						hq.heapify(a__ )

						while h:
												lowerCAmelCase   :Union[str, Any]						=			hq.heappop(a__ )
												for v in u.neighbors:
																		if (v in h) and (u.edges[v.id] < v.key):
																								lowerCAmelCase   :int						=			u
																								lowerCAmelCase   :List[Any]						=			u.edges[v.id]
																								hq.heapify(a__ )

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


def        UpperCAmelCase      (					):





						'''simple docstring'''








if __name__ == "__main__":
		import doctest

		doctest.testmod()