




from __future__ import annotations


class 		lowerCAmelCase_							:





     def __init__(  self       ,   _UpperCAmelCase     )		->							Union[str, Any]:
        lowerCamelCase											=vertices
        lowerCamelCase											=[[0] * vertices for _ in range(__a     )]





     def 	lowerCamelCase       (  self       ,   _UpperCAmelCase     )		->							List[Any]:
        print("""Vertex \t Distance from Source"""     )
        for vertex in range(self.vertices     ):
           print(__a       ,   """\t\t"""       ,   distances_from_source[vertex]     )





     def 	lowerCamelCase       (  self       ,   _UpperCAmelCase       ,   _UpperCAmelCase     )		->							int:
        lowerCamelCase											=1E7
        lowerCamelCase											=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:
              lowerCamelCase											=distances_from_source[vertex]
              lowerCamelCase											=vertex
        return min_index





     def 	lowerCamelCase       (  self       ,   _UpperCAmelCase     )		->							Tuple:
        lowerCamelCase											=[int(1E7     )] * self.vertices  # distances from the source
        lowerCamelCase											=0
        lowerCamelCase											=[False] * self.vertices

        for _ in range(self.vertices     ):
           lowerCamelCase											=self.minimum_distance(__a       ,   __a     )
           lowerCamelCase											=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]
              ):
                 lowerCamelCase											=distances[u] + self.graph[u][v]

        self.print_solution(__a     )


if __name__ == "__main__":
   _UpperCAmelCase				:	Dict    						=    Graph(9)
   _UpperCAmelCase				:	Dict    						=    [
       [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)







import math
from decimal import Decimal, getcontext






def    UpperCAmelCase__	(						lowerCamelCase  : int = 4_00_00_00						):

   try:
      lowerCamelCase											=int(lowerCamelCase						)
   except (TypeError, ValueError):
      raise TypeError("""Parameter n must be int or castable to int."""						)
   if n <= 0:
      raise ValueError("""Parameter n must be greater than or equal to one."""						)
   lowerCamelCase											=1_00
   lowerCamelCase											=(Decimal(5						) ** Decimal(0.5						) + 1) / Decimal(2						)

   lowerCamelCase											=(math.floor(math.log(n * (phi + 2) ,lowerCamelCase						) - 1						) // 3) * 3 + 2
   lowerCamelCase											=Decimal(round(phi ** Decimal(index + 1						)						)						) / (phi + 2)
   lowerCamelCase											=num // 2
   return int(lowerCamelCase						)


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