


'''simple docstring'''

from __future__ import annotations
class 						__lowerCAmelCase		:





      '''simple docstring'''






      def __init__(self					:					List[Any]     ,		UpperCamelCase					:					int				):

             '''simple docstring'''







             lowercase__       =				vertices
             lowercase__       =				[[0] * vertices for _ in range(UpperCamelCase				)]



      def    UpperCamelCase__	(self					:					Optional[Any]     ,		UpperCamelCase					:					list[int]				):

             '''simple docstring'''







             print('''Vertex \t Distance from Source'''				)
             for vertex in range(self.vertices				):
                    print(UpperCamelCase     ,		'''\t\t'''     ,		distances_from_source[vertex]				)



      def    UpperCamelCase__	(self					:					Dict     ,		UpperCamelCase					:					list[int]     ,		UpperCamelCase					:					list[bool]				):

             '''simple docstring'''







             lowercase__       =				1E7
             lowercase__       =				0

             # Search not nearest vertex not in the shortest path tree
             for vertex in range(self.vertices				):
                    if distances_from_source[vertex] < minimum and visited[vertex] is False:
                           lowercase__       =				distances_from_source[vertex]
                           lowercase__       =				vertex
             return min_index






      def    UpperCamelCase__	(self					:					Optional[int]     ,		UpperCamelCase					:					int				):

             '''simple docstring'''







             lowercase__       =				[int(1E7				)] * self.vertices  # distances from the source
             lowercase__       =				0
             lowercase__       =				[False] * self.vertices

             for _ in range(self.vertices				):
                    lowercase__       =				self.minimum_distance(UpperCamelCase     ,		UpperCamelCase				)
                    lowercase__       =				True

                    # Update dist value of the adjacent vertices
                    # of the picked vertex only if the current
                    # distance is greater than new distance and
                    # the vertex in not in the shortest path tree
                    for v in range(self.vertices				):
                           if (
                               self.graph[u][v] > 0
                               and visited[v] is False
                               and distances[v] > distances[u] + self.graph[u][v]
                           ):
                                  lowercase__       =				distances[u] + self.graph[u][v]

             self.print_solution(UpperCamelCase				)


if __name__ == "__main__":
 lowerCamelCase							:     List[Any]								=			Graph(9)
 lowerCamelCase							:     Any								=			[
     [0, 4, 0, 0, 0, 0, 0, 8, 0],
     [4, 0, 8, 0, 0, 0, 0, 11, 0],
     [0, 8, 0, 7, 0, 4, 0, 0, 2],
     [0, 0, 7, 0, 9, 14, 0, 0, 0],
     [0, 0, 0, 9, 0, 10, 0, 0, 0],
     [0, 0, 4, 14, 10, 0, 2, 0, 0],
     [0, 0, 0, 0, 0, 2, 0, 1, 6],
     [8, 11, 0, 0, 0, 0, 1, 0, 7],
     [0, 0, 2, 0, 0, 0, 6, 7, 0],
 ]
 graph.dijkstra(0)








'''simple docstring'''

from __future__ import annotations

from collections import Counter

def _SCREAMING_SNAKE_CASE   (A ) -> list[int]:






       """simple docstring"""







       lowercase__       =				[True] * n
       lowercase__       =				False
       lowercase__       =				False
       lowercase__       =				True

       for i in range(3						,				int(n**0.5 + 1 )						,				2 ):
              lowercase__       =				i * 2
              while index < n:
                     lowercase__       =				False
                     lowercase__       =				index + i

       lowercase__       =				[2]

       for i in range(3						,				A						,				2 ):
              if is_prime[i]:
                     primes.append(A )

       return primes

def _SCREAMING_SNAKE_CASE   (A ) -> list[list[int]]:






       """simple docstring"""







       lowercase__       =				str(A )
       lowercase__       =				[]
       lowercase__       =				['''0''', '''1''', '''2''', '''3''', '''4''', '''5''', '''6''', '''7''', '''8''', '''9''']

       for duplicate in Counter(A ) - Counter(set(A ) ):
              lowercase__       =				[int(number_str.replace(A						,				A ) ) for digit in digits]
              replacements.append(A )

       return replacements

def _SCREAMING_SNAKE_CASE   (A = 8 ) -> int:






       """simple docstring"""







       lowercase__       =				set()

       # Filter primes with less than 3 replaceable digits
       lowercase__       =				{
           x for x in set(prime_sieve(1_000_000 ) ) if len(str(A ) ) - len(set(str(A ) ) ) >= 3
       }

       for prime in primes:
              if prime in numbers_checked:
                     continue

              lowercase__       =				digit_replacements(A )

              for family in replacements:
                     numbers_checked.update(A )
                     lowercase__       =				primes.intersection(A )

                     if len(A ) != family_length:
                            continue

                     return min(A )

       return -1


if __name__ == "__main__":
 print(solution())




