






"""simple docstring"""





from __future__ import annotations

from typing import Any
class    __lowerCamelCase    :

   def __init__(					self ,				snake_case_      )		->       None:
       UpperCamelCase__         =    num_of_nodes
       UpperCamelCase__         =    []
       UpperCamelCase__         =    {}

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_ ,				snake_case_ ,				snake_case_      )		->       None:
       self.m_edges.append([u_node, v_node, weight]      )

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_      )		->       int:

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

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_      )		->       None:

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

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_ ,				snake_case_ ,				snake_case_      )		->       None:

       if component_size[u_node] <= component_size[v_node]:
           UpperCamelCase__         =    v_node
           component_size[v_node] += component_size[u_node]
           self.set_component(snake_case_      )

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







   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       None:
       UpperCamelCase__         =    []
       UpperCamelCase__         =    0

       UpperCamelCase__         =    [-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__         =    self.m_num_of_nodes

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

               UpperCamelCase__         =    self.m_component[u]
               UpperCamelCase__         =    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__         =    [u, v, w]

           for edge in minimum_weight_edge:
               if isinstance(snake_case_ ,				snake_case_      ):
                   UpperCamelCase__       ,						UpperCamelCase__       ,						UpperCamelCase__         =    edge

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

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

           UpperCamelCase__         =    [-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()












"""simple docstring"""





from __future__ import annotations

from typing import Generic, TypeVar

A__					: Any=	TypeVar("""T""")
class    __lowerCamelCase    (  Generic[T]  ):

   def __init__(					self ,				snake_case_      )		->       None:
       UpperCamelCase__         =    data
       UpperCamelCase__         =    self
       UpperCamelCase__         =    0







class    __lowerCamelCase    (  Generic[T]  ):

   def __init__(					self      )		->       None:
       # map from node name to the node object
       UpperCamelCase__         =    {}

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_      )		->       None:
       # create a new set with x as its member
       UpperCamelCase__         =    DisjointSetTreeNode(snake_case_      )

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_      )		->       DisjointSetTreeNode[T]:
       # find the set x belongs to (with path-compression)
       UpperCamelCase__         =    self.map[data]
       if elem_ref != elem_ref.parent:
           UpperCamelCase__         =    self.find_set(elem_ref.parent.data      )
       return elem_ref.parent

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_ ,				snake_case_      )		->       None:
       # helper function for union operation
       if nodea.rank > nodea.rank:
           UpperCamelCase__         =    nodea
       else:
           UpperCamelCase__         =    nodea
           if nodea.rank == nodea.rank:
               nodea.rank += 1







   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_ ,				snake_case_      )		->       None:
       # merge 2 disjoint sets
       self.link(self.find_set(snake_case_      ) ,				self.find_set(snake_case_      )      )







class    __lowerCamelCase    (  Generic[T]  ):

   def __init__(					self      )		->       None:
       # connections: map from the node to the neighbouring nodes (with weights)
       UpperCamelCase__         =    {}

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_      )		->       None:
       # add a node ONLY if its not present in the graph
       if node not in self.connections:
           UpperCamelCase__         =    {}

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_ ,				snake_case_ ,				snake_case_      )		->       None:
       # add an edge with the given weight
       self.add_node(snake_case_      )
       self.add_node(snake_case_      )
       UpperCamelCase__         =    weight
       UpperCamelCase__         =    weight







   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       GraphUndirectedWeighted[T]:
       UpperCamelCase__         =    []
       UpperCamelCase__         =    set()
       for start in self.connections:
           for end in self.connections[start]:
               if (start, end) not in seen:
                   seen.add((end, start)      )
                   edges.append((start, end, self.connections[start][end])      )
       edges.sort(key=lambda snake_case_      : x[2]      )

       # creating the disjoint set
       UpperCamelCase__         =    DisjointSetTree[T]()
       for node in self.connections:
           disjoint_set.make_set(snake_case_      )

       # MST generation
       UpperCamelCase__         =    0
       UpperCamelCase__         =    0
       UpperCamelCase__         =    GraphUndirectedWeighted[T]()
       while num_edges < len(self.connections      ) - 1:
           UpperCamelCase__       ,						UpperCamelCase__       ,						UpperCamelCase__         =    edges[index]
           index += 1
           UpperCamelCase__         =    disjoint_set.find_set(snake_case_      )
           UpperCamelCase__         =    disjoint_set.find_set(snake_case_      )
           if parent_u != parent_v:
               num_edges += 1
               graph.add_edge(snake_case_ ,				snake_case_ ,				snake_case_      )
               disjoint_set.union(snake_case_ ,				snake_case_      )
       return graph




