


"""simple docstring"""







from __future__ import annotations

from typing import Any




class 				UpperCamelCase_			:

	"""simple docstring"""





	def __init__(				self    :       Any    ,    UpperCAmelCase__    :       int     ) ->			None:
						__SCREAMING_SNAKE_CASE		     =       num_of_nodes
						__SCREAMING_SNAKE_CASE		     =       []
						__SCREAMING_SNAKE_CASE		     =       {}




	def 						UpperCAmelCase_   (				self    :       Union[str, Any]    ,    UpperCAmelCase__    :       int    ,    UpperCAmelCase__    :       int    ,    UpperCAmelCase__    :       int     ) ->			None:
						self.m_edges.append([u_node, v_node, weight]     )




	def 						UpperCAmelCase_   (				self    :       Tuple    ,    UpperCAmelCase__    :       int     ) ->			int:

						if self.m_component[u_node] == u_node:
											return u_node
						return self.find_component(self.m_component[u_node]     )




	def 						UpperCAmelCase_   (				self    :       str    ,    UpperCAmelCase__    :       int     ) ->			None:

						if self.m_component[u_node] != u_node:
											for k in self.m_component:
																__SCREAMING_SNAKE_CASE		     =       self.find_component(UpperCAmelCase__     )




	def 						UpperCAmelCase_   (				self    :       Dict    ,    UpperCAmelCase__    :       list[int]    ,    UpperCAmelCase__    :       int    ,    UpperCAmelCase__    :       int     ) ->			None:

						if component_size[u_node] <= component_size[v_node]:
											__SCREAMING_SNAKE_CASE		     =       v_node
											component_size[v_node] += component_size[u_node]
											self.set_component(UpperCAmelCase__     )

						elif component_size[u_node] >= component_size[v_node]:
											__SCREAMING_SNAKE_CASE		     =       self.find_component(UpperCAmelCase__     )
											component_size[u_node] += component_size[v_node]
											self.set_component(UpperCAmelCase__     )




	def 						UpperCAmelCase_   (				self    :       Optional[Any]     ) ->			None:
						__SCREAMING_SNAKE_CASE		     =       []
						__SCREAMING_SNAKE_CASE		     =       0

						__SCREAMING_SNAKE_CASE		     =       [-1] * self.m_num_of_nodes

						# A list of components (initialized to all of the nodes)
						for node in range(self.m_num_of_nodes     ):
											self.m_component.update({node: node}     )
											component_size.append(1     )

						__SCREAMING_SNAKE_CASE		     =       self.m_num_of_nodes

						while num_of_components > 1:
											for edge in self.m_edges:
																__SCREAMING_SNAKE_CASE     ,						__SCREAMING_SNAKE_CASE     ,						__SCREAMING_SNAKE_CASE		     =       edge

																__SCREAMING_SNAKE_CASE		     =       self.m_component[u]
																__SCREAMING_SNAKE_CASE		     =       self.m_component[v]

																if u_component != v_component:

																					for component in (u_component, v_component):
																										if (
																										    minimum_weight_edge[component] == -1
																										    or minimum_weight_edge[component][2] > w
																										):
																															__SCREAMING_SNAKE_CASE		     =       [u, v, w]

											for edge in minimum_weight_edge:
																if isinstance(UpperCAmelCase__    ,    UpperCAmelCase__     ):
																					__SCREAMING_SNAKE_CASE     ,						__SCREAMING_SNAKE_CASE     ,						__SCREAMING_SNAKE_CASE		     =       edge

																					__SCREAMING_SNAKE_CASE		     =       self.m_component[u]
																					__SCREAMING_SNAKE_CASE		     =       self.m_component[v]

																					if u_component != v_component:
																										mst_weight += w
																										self.union(UpperCAmelCase__    ,    UpperCAmelCase__    ,    UpperCAmelCase__     )
																										print(F"""Added edge [{u} - {v}]\nAdded weight: {w}\n"""     )
																										num_of_components -= 1

											__SCREAMING_SNAKE_CASE		     =       [-1] * self.m_num_of_nodes
						print(F"""The total weight of the minimal spanning tree is: {mst_weight}"""     )




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