






from __future__ import annotations

from typing import Any







class 				UpperCAmelCase_  :




     def __init__(				self	,						_lowerCAmelCase		):
          UpperCAmelCase__      :  int				      =			num_of_nodes
          UpperCAmelCase__      :  list[list[int]]				      =			[]
          UpperCAmelCase__      :  dict[int, int]				      =			{}




     def   __UpperCAmelCase  (				self	,						_lowerCAmelCase	,						_lowerCAmelCase	,						_lowerCAmelCase		):
          self.m_edges.append([u_node, v_node, weight]		)




     def   __UpperCAmelCase  (				self	,						_lowerCAmelCase		):

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




     def   __UpperCAmelCase  (				self	,						_lowerCAmelCase		):

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




     def   __UpperCAmelCase  (				self	,						_lowerCAmelCase	,						_lowerCAmelCase	,						_lowerCAmelCase		):

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

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




     def   __UpperCAmelCase  (				self		):
          UpperCAmelCase__      :  List[str]				      =			[]
          UpperCAmelCase__      :  Tuple				      =			0

          UpperCAmelCase__      :  list[Any]				      =			[-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		)

          UpperCAmelCase__      :  Optional[Any]				      =			self.m_num_of_nodes

          while num_of_components > 1:
               for edge in self.m_edges:
                    UpperCAmelCase__      ,		UpperCAmelCase__      ,		UpperCAmelCase__      :  Optional[Any]				      =			edge

                    UpperCAmelCase__      :  List[str]				      =			self.m_component[u]
                    UpperCAmelCase__      :  Optional[Any]				      =			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
                              ):
                                   UpperCAmelCase__      :  Union[str, Any]				      =			[u, v, w]

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

                         UpperCAmelCase__      :  str				      =			self.m_component[u]
                         UpperCAmelCase__      :  Union[str, Any]				      =			self.m_component[v]

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

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





def  _lowerCamelCase						(						) ->			None:

     '''simple docstring'''


if __name__ == "__main__":
      import doctest

      doctest.testmod()











from bisect import bisect
from itertools import accumulate






def  lowerCamelCase_	(      lowerCAmelCase__	:	int			,	lowerCAmelCase__	:	str			,	lowerCAmelCase__	:	List[str]			,	lowerCAmelCase__	:	List[Any]				)       ->							Union[str, Any]:

							'''simple docstring'''






							A      						=    sorted(zip(lowerCAmelCase__			,	lowerCAmelCase__				)			,	key=lambda lowerCAmelCase__				: x[0] / x[1]			,	reverse=lowerCAmelCase__				)
							A						,   A      						=    [i[0] for i in r], [i[1] for i in r]
							A      						=    list(accumulate(lowerCAmelCase__				)				)
							A      						=    bisect(lowerCAmelCase__			,	lowerCAmelCase__				)
							return (
							    0
							    if k == 0
							    else sum(vl[:k]				) + (w - acc[k - 1]) * (vl[k]) / (wt[k])
							    if k != n
							    else sum(vl[:k]				)
							)


if __name__ == "__main__":
				import doctest

				doctest.testmod()