


"""simple docstring"""
from __future__ import annotations

import os
from collections.abc import Mapping

UpperCAmelCase				=						tuple[int, int]




class 	lowercase__				:





   def __init__(							self      ,   SCREAMING_SNAKE_CASE      ,   SCREAMING_SNAKE_CASE)  ->  None:
      _lowerCamelCase	:					set[int]   =		vertices
      _lowerCamelCase	:					dict[EdgeT, int]   =		{
          (min(SCREAMING_SNAKE_CASE), max(SCREAMING_SNAKE_CASE)): weight for edge, weight in edges.items()
      }





   def 		UpperCamelCase_  (							self      ,   SCREAMING_SNAKE_CASE      ,   SCREAMING_SNAKE_CASE)  ->  None:
      self.vertices.add(edge[0])
      self.vertices.add(edge[1])
      _lowerCamelCase	:					Optional[int]   =		weight





   def 		UpperCamelCase_  (							self)  ->  Graph:
      _lowerCamelCase	:					Graph   =		Graph({min(self.vertices)}      ,   {})
      _lowerCamelCase	:					EdgeT
      _lowerCamelCase	:					int
      _lowerCamelCase	:					EdgeT
      _lowerCamelCase	:					int

      while len(subgraph.vertices) < len(self.vertices):
         _lowerCamelCase	:					List[str]   =		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:
                  _lowerCamelCase	:					int   =		edge
                  _lowerCamelCase	:					List[Any]   =		weight

         subgraph.add_edge(SCREAMING_SNAKE_CASE      ,   SCREAMING_SNAKE_CASE)

      return subgraph







def 				_snake_case      (   __snake_case							:      str = "p107_network.txt"   ):




   """simple docstring"""







   _lowerCamelCase	:					str   =		os.path.abspath(os.path.dirname(__snake_case   )   )
   _lowerCamelCase	:					str   =		os.path.join(__snake_case						, __snake_case   )
   _lowerCamelCase	:					dict[EdgeT, int]   =		{}
   _lowerCamelCase	:					list[str]
   _lowerCamelCase	:					int
   _lowerCamelCase	:					int

   with open(__snake_case   ) as f:
      _lowerCamelCase	:					Optional[Any]   =		f.read().strip().split("""\n"""   )

   _lowerCamelCase	:					List[str]   =		[line.split(""","""   ) for line in data]

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

   _lowerCamelCase	:					Graph   =		Graph(set(range(len(__snake_case   )   )   )						, __snake_case   )

   _lowerCamelCase	:					Graph   =		graph.prims_algorithm()

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

   return initial_total - optimal_total


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





"""simple docstring"""
def 				_snake_case      (   __snake_case							:      list[list[int]]						, __snake_case							:      int						, __snake_case							:      int						, __snake_case							:      list[int]   ):




   """simple docstring"""







   if graph[path[curr_ind - 1]][next_ver] == 0:
      return False

   # 2. Validate that next vertex is not already in path
   return not any(vertex == next_ver for vertex in path   )

def 				_snake_case      (   __snake_case							:      list[list[int]]						, __snake_case							:      list[int]						, __snake_case							:      int   ):




   """simple docstring"""







   if curr_ind == len(__snake_case   ):
      # return whether path exists between current and starting vertices
      return graph[path[curr_ind - 1]][path[0]] == 1

   # Recursive Step
   for next_ver in range(0						, len(__snake_case   )   ):
      if valid_connection(__snake_case						, __snake_case						, __snake_case						, __snake_case   ):
         # Insert current vertex  into path as next transition
         _lowerCamelCase	:					List[str]   =		next_ver
         # Validate created path
         if util_hamilton_cycle(__snake_case						, __snake_case						, curr_ind + 1   ):
            return True
         # Backtrack
         _lowerCamelCase	:					Tuple   =		-1
   return False





def 				_snake_case      (   __snake_case							:      list[list[int]]						, __snake_case							:      int = 0   ):




   """simple docstring"""







   _lowerCamelCase	:					Any   =		[-1] * (len(__snake_case   ) + 1)
   # initialize start and end of path with starting index
   _lowerCamelCase	:					Optional[int]   =		start_index
   # evaluate and if we find answer return path either return empty array
   return path if util_hamilton_cycle(__snake_case						, __snake_case						, 1   ) else []

