




from __future__ import annotations

from typing import Any







class   A:



 '''simple docstring'''


 def __init__(				self					:  str						,							A_					:  int  )   ->	None:

       """simple docstring"""






       lowerCamelCase_		     =    num_of_nodes
       lowerCamelCase_		     =    []
       lowerCamelCase_		     =    {}

 def 				a__ (				self					:  Optional[int]						,							A_					:  int						,							A_					:  int						,							A_					:  int  )   ->	None:

       """simple docstring"""






       self.m_edges.append([u_node, v_node, weight]  )

 def 				a__ (				self					:  List[str]						,							A_					:  int  )   ->	int:

       """simple docstring"""






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

 def 				a__ (				self					:  List[Any]						,							A_					:  int  )   ->	None:

       """simple docstring"""






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

 def 				a__ (				self					:  str						,							A_					:  list[int]						,							A_					:  int						,							A_					:  int  )   ->	None:

       """simple docstring"""






       if component_size[u_node] <= component_size[v_node]:
             lowerCamelCase_		     =    v_node
             component_size[v_node] += component_size[u_node]
             self.set_component(A_  )

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





 def 				a__ (				self					:  Any  )   ->	None:

       """simple docstring"""






       lowerCamelCase_		     =    []
       lowerCamelCase_		     =    0

       lowerCamelCase_		     =    [-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  )

       lowerCamelCase_		     =    self.m_num_of_nodes

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

                   lowerCamelCase_		     =    self.m_component[u]
                   lowerCamelCase_		     =    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
                               ):
                                     lowerCamelCase_		     =    [u, v, w]

             for edge in minimum_weight_edge:
                   if isinstance(A_						,							A_  ):
                         lowerCamelCase_     ,				lowerCamelCase_     ,				lowerCamelCase_		     =    edge

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

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

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

def 			_SCREAMING_SNAKE_CASE			(							):


      '''simple docstring'''





if __name__ == "__main__":
 import doctest

 doctest.testmod()









def 			_SCREAMING_SNAKE_CASE			(							lowercase	:       list     ):


      '''simple docstring'''



      for i in range(len(lowercase     ) - 1	,							0	,							-1     ):
            lowerCamelCase_		     =    False

            for j in range(lowercase	,							0	,							-1     ):
                  if unsorted[j] < unsorted[j - 1]:
                        lowerCamelCase_     ,				lowerCamelCase_		     =    unsorted[j - 1], unsorted[j]
                        lowerCamelCase_		     =    True

            for j in range(lowercase     ):
                  if unsorted[j] > unsorted[j + 1]:
                        lowerCamelCase_     ,				lowerCamelCase_		     =    unsorted[j + 1], unsorted[j]
                        lowerCamelCase_		     =    True

            if not swapped:
                  break
      return unsorted


if __name__ == "__main__":
 import doctest

 doctest.testmod()
 lowerCamelCase				:		Any     =   input("Enter numbers separated by a comma:\n").strip()
 lowerCamelCase				:		Dict     =   [int(item) for item in user_input.split(",")]
 print(F"""{cocktail_shaker_sort(unsorted) = }""")



