






from __future__ import annotations

from typing import Any


class 						_a       :






  """simple docstring"""





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




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




  def    _UpperCAmelCase     (     self		,		_UpperCAmelCase )			-> int:

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




  def    _UpperCAmelCase     (     self		,		_UpperCAmelCase )			-> None:

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




  def    _UpperCAmelCase     (     self		,		_UpperCAmelCase		,		_UpperCAmelCase		,		_UpperCAmelCase )			-> None:

     if component_size[u_node] <= component_size[v_node]:
        UpperCamelCase_									=     v_node
        component_size[v_node] += component_size[u_node]
        self.set_component(_UpperCAmelCase )

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




  def    _UpperCAmelCase     (     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(_UpperCAmelCase		,		_UpperCAmelCase ):
              UpperCamelCase_		,      UpperCamelCase_		,      UpperCamelCase_									=     edge

              UpperCamelCase_									=     self.m_component[u]
              UpperCamelCase_									=     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

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






def     _snake_case    ():
   pass


if __name__ == "__main__":
 import doctest

 doctest.testmod()













snake_case__      :	List[Any]       	=      """Tobias Carryer"""

from time import time


class 						_a       :






  """simple docstring"""





  def __init__(     self		,		_UpperCAmelCase		,		_UpperCAmelCase		,		_UpperCAmelCase		,		_UpperCAmelCase=int(time() ) )			-> Tuple:  # noqa: B008
     UpperCamelCase_									=     multiplier
     UpperCamelCase_									=     increment
     UpperCamelCase_									=     modulo
     UpperCamelCase_									=     seed




  def    _UpperCAmelCase     (     self )			-> Any:
     UpperCamelCase_									=     (self.multiplier * self.seed + self.increment) % self.modulo
     return self.seed


if __name__ == "__main__":
 # Show the LCG in action.
 snake_case__      :	List[Any]       	=      LinearCongruentialGenerator(1_6_6_4_5_2_5, 1_0_1_3_9_0_4_2_2_3, 2 << 3_1)
 while True:
  print(lcg.next_number())





