





from __future__ import annotations

import os
from collections.abc import Mapping

A__:    Any  	=	tuple[int, int]




class        _a    :

      """simple docstring"""


      def __init__(		self:			Optional[Any]	,    __lowerCamelCase:			set[int]	,    __lowerCamelCase:			Mapping[EdgeT, int]					):
          '''simple docstring'''


          UpperCamelCase__:	set[int]					=     vertices
          UpperCamelCase__:	dict[EdgeT, int]					=     {
              (min(__lowerCamelCase					), max(__lowerCamelCase					)): weight for edge, weight in edges.items()
          }






      def 			UpperCAmelCase_       (		self:			Optional[Any]	,    __lowerCamelCase:			EdgeT	,    __lowerCamelCase:			int					):
          '''simple docstring'''


          self.vertices.add(edge[0]					)
          self.vertices.add(edge[1]					)
          UpperCamelCase__:	Optional[int]					=     weight






      def 			UpperCAmelCase_       (		self:			int					):
          '''simple docstring'''


          UpperCamelCase__:	Graph					=     Graph({min(self.vertices					)}	,    {}					)
          UpperCamelCase__:	EdgeT
          UpperCamelCase__:	int
          UpperCamelCase__:	EdgeT
          UpperCamelCase__:	int

          while len(subgraph.vertices					) < len(self.vertices					):
              UpperCamelCase__:	Any					=     max(self.edges.values()					) + 1
              for edge, weight in self.edges.items():
                  if (edge[0] in subgraph.vertices) ^ (edge[1] in subgraph.vertices):
                      if weight < min_weight:
                          UpperCamelCase__:	Optional[Any]					=     edge
                          UpperCamelCase__:	Tuple					=     weight

              subgraph.add_edge(__lowerCamelCase	,    __lowerCamelCase					)

          return subgraph



def 				lowerCAmelCase_ (							A_ = "p107_network.txt"):
    UpperCamelCase__:	str					=     os.path.abspath(os.path.dirname(A_))
    UpperCamelCase__:	str					=     os.path.join(A_    ,A_)
    UpperCamelCase__:	dict[EdgeT, int]					=     {}
    UpperCamelCase__:	list[str]
    UpperCamelCase__:	int
    UpperCamelCase__:	int

    with open(A_) as f:
        UpperCamelCase__:	List[str]					=     f.read().strip().split("\n")

    UpperCamelCase__:	Optional[int]					=     [line.split(",") for line in data]

    for edgea in range(1    ,len(A_)):
        for edgea in range(A_):
            if adjaceny_matrix[edgea][edgea] != "-":
                UpperCamelCase__:	str					=     int(adjaceny_matrix[edgea][edgea])

    UpperCamelCase__:	Graph					=     Graph(set(range(len(A_)))    ,A_)

    UpperCamelCase__:	Graph					=     graph.prims_algorithm()

    UpperCamelCase__:	int					=     sum(graph.edges.values())
    UpperCamelCase__:	int					=     sum(subgraph.edges.values())

    return initial_total - optimal_total


if __name__ == "__main__":
   print(f"{solution() = }")








from __future__ import annotations

from typing import Any




class        _a    :

      """simple docstring"""


      def __init__(		self:			Optional[int]	,    __lowerCamelCase:			int					):
          '''simple docstring'''


          UpperCamelCase__:	Optional[Any]					=     num_of_nodes
          UpperCamelCase__:	list[list[int]]					=     []
          UpperCamelCase__:	dict[int, int]					=     {}






      def 			UpperCAmelCase_       (		self:			Any	,    __lowerCamelCase:			int	,    __lowerCamelCase:			int	,    __lowerCamelCase:			int					):
          '''simple docstring'''


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






      def 			UpperCAmelCase_       (		self:			Dict	,    __lowerCamelCase:			int					):
          '''simple docstring'''


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






      def 			UpperCAmelCase_       (		self:			str	,    __lowerCamelCase:			int					):
          '''simple docstring'''


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






      def 			UpperCAmelCase_       (		self:			str	,    __lowerCamelCase:			list[int]	,    __lowerCamelCase:			int	,    __lowerCamelCase:			int					):
          '''simple docstring'''


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

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






      def 			UpperCAmelCase_       (		self:			Tuple					):
          '''simple docstring'''


          UpperCamelCase__:	Optional[int]					=     []
          UpperCamelCase__:	Optional[int]					=     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[int]					=     self.m_num_of_nodes

          while num_of_components > 1:
              for edge in self.m_edges:
                  UpperCamelCase__				, UpperCamelCase__				, UpperCamelCase__:	List[str]					=     edge

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

              for edge in minimum_weight_edge:
                  if isinstance(__lowerCamelCase	,    __lowerCamelCase					):
                      UpperCamelCase__				, UpperCamelCase__				, UpperCamelCase__:	List[str]					=     edge

                      UpperCamelCase__:	Tuple					=     self.m_component[u]
                      UpperCamelCase__:	Optional[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__:	List[Any]					=     [-1] * self.m_num_of_nodes
          print(F"The total weight of the minimal spanning tree is: {mst_weight}"					)



def 				lowerCAmelCase_ (							):
    pass


if __name__ == "__main__":
   import doctest

   doctest.testmod()

