


"""simple docstring"""







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




class 				UpperCamelCase_			:

	"""simple docstring"""





	def __init__(				self    :       List[Any]    ,    UpperCAmelCase__    :       Optional[Any]     ) ->			str:
						__SCREAMING_SNAKE_CASE		     =       str(id_     )
						__SCREAMING_SNAKE_CASE		     =       None
						__SCREAMING_SNAKE_CASE		     =       None
						__SCREAMING_SNAKE_CASE		     =       []
						__SCREAMING_SNAKE_CASE		     =       {}  # {vertex:distance}




	def __lt__(				self    :       str    ,    UpperCAmelCase__    :       Union[str, Any]     ) ->			Optional[Any]:
						return self.key < other.key




	def __repr__(				self    :       List[Any]     ) ->			List[Any]:
						return self.id




	def 						UpperCAmelCase_   (				self    :       List[Any]    ,    UpperCAmelCase__    :       Tuple     ) ->			Optional[int]:
						self.neighbors.append(UpperCAmelCase__     )




	def 						UpperCAmelCase_   (				self    :       Optional[int]    ,    UpperCAmelCase__    :       str    ,    UpperCAmelCase__    :       Union[str, Any]     ) ->			int:
						__SCREAMING_SNAKE_CASE		     =       weight




def      UpperCAmelCase__ (lowerCAmelCase_						,		lowerCAmelCase_						,		lowerCAmelCase_						,		lowerCAmelCase_     ):




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




def      UpperCAmelCase__ (lowerCAmelCase_						,		lowerCAmelCase_     ):




					'''simple docstring'''


					__SCREAMING_SNAKE_CASE		     =       []
					for u in graph:
										__SCREAMING_SNAKE_CASE		     =       math.inf
										__SCREAMING_SNAKE_CASE		     =       None
					__SCREAMING_SNAKE_CASE		     =       0
					__SCREAMING_SNAKE_CASE		     =       graph[:]
					while q:
										__SCREAMING_SNAKE_CASE		     =       min(lowerCAmelCase_     )
										q.remove(lowerCAmelCase_     )
										for v in u.neighbors:
															if (v in q) and (u.edges[v.id] < v.key):
																				__SCREAMING_SNAKE_CASE		     =       u
																				__SCREAMING_SNAKE_CASE		     =       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      UpperCAmelCase__ (lowerCAmelCase_						,		lowerCAmelCase_     ):




					'''simple docstring'''


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

					__SCREAMING_SNAKE_CASE		     =       list(lowerCAmelCase_     )
					hq.heapify(lowerCAmelCase_     )

					while h:
										__SCREAMING_SNAKE_CASE		     =       hq.heappop(lowerCAmelCase_     )
										for v in u.neighbors:
															if (v in h) and (u.edges[v.id] < v.key):
																				__SCREAMING_SNAKE_CASE		     =       u
																				__SCREAMING_SNAKE_CASE		     =       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      UpperCAmelCase__ ():




					'''simple docstring'''




if __name__ == "__main__":
		import doctest

		doctest.testmod()




"""simple docstring"""







from __future__ import annotations




def      UpperCAmelCase__ (lowerCAmelCase_     ):




					'''simple docstring'''


					if len(lowerCAmelCase_     ) < 2:
										raise ValueError("Monogons and Digons are not polygons in the Euclidean space"     )
					if any(i <= 0 for i in nums     ):
										raise ValueError("All values must be greater than 0"     )
					__SCREAMING_SNAKE_CASE		     =       nums.copy()
					copy_nums.sort()
					return copy_nums[-1] < sum(copy_nums[:-1]     )


if __name__ == "__main__":
		import doctest

		doctest.testmod()
