






'''simple docstring'''





import math
import unittest
def __UpperCAmelCase   (					A					:			int		)    ->   bool:
			assert isinstance(A			,       A		) and (
			    number >= 0
			), "'number' must been an int and positive"

			if 1 < number < 4:
						# 2 and 3 are primes
						return True
			elif number < 2 or number % 2 == 0 or number % 3 == 0:
						# Negatives, 0, 1, all even numbers, all multiples of 3 are not primes
						return False

			# All primes number are in format of 6k +/- 1
			for i in range(5			,       int(math.sqrt(A		) + 1		)			,       6		):
						if number % i == 0 or number % (i + 2) == 0:
									return False
			return True


class  snake_case__      (					unittest.TestCase):




					def 		A      (  self  :		Dict      )    ->							int:
								self.assertTrue(is_prime(2      )      )
								self.assertTrue(is_prime(3      )      )
								self.assertTrue(is_prime(5      )      )
								self.assertTrue(is_prime(7      )      )
								self.assertTrue(is_prime(11      )      )
								self.assertTrue(is_prime(13      )      )
								self.assertTrue(is_prime(17      )      )
								self.assertTrue(is_prime(19      )      )
								self.assertTrue(is_prime(23      )      )
								self.assertTrue(is_prime(29      )      )





					def 		A      (  self  :		int      )    ->							List[str]:
								with self.assertRaises(_A      ):
											is_prime(-19      )
								self.assertFalse(
								    is_prime(0      )				, '''Zero doesn\'t have any positive factors, primes must have exactly two.'''				, )
								self.assertFalse(
								    is_prime(1      )				, '''One only has 1 positive factor, primes must have exactly two.'''				, )
								self.assertFalse(is_prime(2 * 2      )      )
								self.assertFalse(is_prime(2 * 3      )      )
								self.assertFalse(is_prime(3 * 3      )      )
								self.assertFalse(is_prime(3 * 5      )      )
								self.assertFalse(is_prime(3 * 5 * 7      )      )


if __name__ == "__main__":
						unittest.main()










'''simple docstring'''





from __future__ import annotations

import os
from collections.abc import Mapping

_UpperCamelCase						:						Any  =					tuple[int, int]


class  snake_case__      :




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




					def 		A      (  self  :		Union[str, Any]				, _A  :		EdgeT				, _A  :		int      )    ->							None:
								self.vertices.add(edge[0]      )
								self.vertices.add(edge[1]      )
								UpperCAmelCase_      :       List[str]          =       weight





					def 		A      (  self  :		str      )    ->							Graph:
								UpperCAmelCase_      :       Graph          =       Graph({min(self.vertices      )}				, {}      )
								UpperCAmelCase_      :       EdgeT
								UpperCAmelCase_      :       int
								UpperCAmelCase_      :       EdgeT
								UpperCAmelCase_      :       int

								while len(subgraph.vertices      ) < len(self.vertices      ):
											UpperCAmelCase_      :       Optional[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_      :       Dict          =       edge
																				UpperCAmelCase_      :       Tuple          =       weight

											subgraph.add_edge(_A				, _A      )

								return subgraph






def __UpperCAmelCase   (					A					:			str = "p107_network.txt"		)    ->   int:
			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_      :       int          =       f.read().strip().split('''\n'''		)

			UpperCAmelCase_      :       Any          =       [line.split(''','''		) for line in data]

			for edgea in range(1			,       len(A		)		):
						for edgea in range(A		):
									if adjaceny_matrix[edgea][edgea] != "-":
												UpperCAmelCase_      :       Optional[int]          =       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() = }''')


