





'''simple docstring'''

from __future__ import annotations

import os
from collections.abc import Mapping

a        =						tuple[int, int]







class __a :





   def __init__(					self				:			List[Any]				,lowerCamelCase				:			set[int]				,lowerCamelCase				:			Mapping[EdgeT, int]    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       vertices
      __SCREAMING_SNAKE_CASE      							=       {
          (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]    )
      __SCREAMING_SNAKE_CASE      							=       weight





   def      UpperCAmelCase__     (					self				:			Union[str, Any]    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       Graph({min(self.vertices    )}				,{}    )
      __SCREAMING_SNAKE_CASE      							=       42
      __SCREAMING_SNAKE_CASE      							=       42
      __SCREAMING_SNAKE_CASE      							=       42
      __SCREAMING_SNAKE_CASE      							=       42

      while len(subgraph.vertices    ) < len(self.vertices    ):
         __SCREAMING_SNAKE_CASE      							=       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:
                  __SCREAMING_SNAKE_CASE      							=       edge
                  __SCREAMING_SNAKE_CASE      							=       weight

         subgraph.add_edge(lowerCamelCase				,lowerCamelCase    )

      return subgraph





def 						__magic_name__       (							__UpperCAmelCase = "p107_network.txt"      )						->					int:

   '''simple docstring'''







   __SCREAMING_SNAKE_CASE      							=       os.path.abspath(os.path.dirname(__UpperCAmelCase      )      )
   __SCREAMING_SNAKE_CASE      							=       os.path.join(__UpperCAmelCase							,	__UpperCAmelCase      )
   __SCREAMING_SNAKE_CASE      							=       {}
   __SCREAMING_SNAKE_CASE      							=       42
   __SCREAMING_SNAKE_CASE      							=       42
   __SCREAMING_SNAKE_CASE      							=       42

   with open(__UpperCAmelCase      ) as f:
      __SCREAMING_SNAKE_CASE      							=       f.read().strip().split("""\n"""      )

   __SCREAMING_SNAKE_CASE      							=       [line.split(""","""      ) for line in data]

   for edgea in range(1							,	len(__UpperCAmelCase      )      ):
      for edgea in range(__UpperCAmelCase      ):
         if adjaceny_matrix[edgea][edgea] != "-":
            __SCREAMING_SNAKE_CASE      							=       int(adjaceny_matrix[edgea][edgea]      )

   __SCREAMING_SNAKE_CASE      							=       Graph(set(range(len(__UpperCAmelCase      )      )      )							,	__UpperCAmelCase      )

   __SCREAMING_SNAKE_CASE      							=       graph.prims_algorithm()

   __SCREAMING_SNAKE_CASE      							=       sum(graph.edges.values()      )
   __SCREAMING_SNAKE_CASE      							=       sum(subgraph.edges.values()      )

   return initial_total - optimal_total


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







'''simple docstring'''

def 						__magic_name__       (							__UpperCAmelCase = 1							,	__UpperCAmelCase = 1000      )						->					int:

   '''simple docstring'''







   __SCREAMING_SNAKE_CASE      							=       1
   __SCREAMING_SNAKE_CASE      							=       0

   for divide_by_number in range(__UpperCAmelCase							,	digit + 1      ):
      __SCREAMING_SNAKE_CASE      							=       []
      __SCREAMING_SNAKE_CASE      							=       numerator
      for _ in range(1							,	digit + 1      ):
         if now_divide in has_been_divided:
            if longest_list_length < len(__UpperCAmelCase      ):
               __SCREAMING_SNAKE_CASE      							=       len(__UpperCAmelCase      )
               __SCREAMING_SNAKE_CASE      							=       divide_by_number
         else:
            has_been_divided.append(__UpperCAmelCase      )
            __SCREAMING_SNAKE_CASE      							=       now_divide * 10 % divide_by_number

   return the_digit


# Tests
if __name__ == "__main__":
    import doctest

    doctest.testmod()





