



from __future__ import annotations

class    _SCREAMING_SNAKE_CASE						:





     def __init__(							self			:				Optional[Any]  ,	UpperCamelCase			:				int					)->None:
      __SCREAMING_SNAKE_CASE							:     Tuple							=						vertices
      __SCREAMING_SNAKE_CASE							:     str							=						[[0] * vertices for _ in range(UpperCamelCase					)]





     def 						__snake_case     (							self			:				Any  ,	UpperCamelCase			:				list[int]					)->None:
      print("Vertex \t Distance from Source"					)
      for vertex in range(self.vertices					):
       print(UpperCamelCase  ,	"\t\t"  ,	distances_from_source[vertex]					)





     def 						__snake_case     (							self			:				Union[str, Any]  ,	UpperCamelCase			:				list[int]  ,	UpperCamelCase			:				list[bool]					)->int:
      __SCREAMING_SNAKE_CASE							:     Dict							=						1E7
      __SCREAMING_SNAKE_CASE							:     Optional[Any]							=						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:
        __SCREAMING_SNAKE_CASE							:     Optional[int]							=						distances_from_source[vertex]
        __SCREAMING_SNAKE_CASE							:     List[str]							=						vertex
      return min_index






     def 						__snake_case     (							self			:				str  ,	UpperCamelCase			:				int					)->None:
      __SCREAMING_SNAKE_CASE							:     int							=						[int(1E7					)] * self.vertices  # distances from the source
      __SCREAMING_SNAKE_CASE							:     Optional[int]							=						0
      __SCREAMING_SNAKE_CASE							:     Optional[int]							=						[False] * self.vertices

      for _ in range(self.vertices					):
       __SCREAMING_SNAKE_CASE							:     Tuple							=						self.minimum_distance(UpperCamelCase  ,	UpperCamelCase					)
       __SCREAMING_SNAKE_CASE							:     List[Any]							=						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]
        ):
         __SCREAMING_SNAKE_CASE							:     Optional[int]							=						distances[u] + self.graph[u][v]

      self.print_solution(UpperCamelCase					)


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

def     __UpperCamelCase					(				_lowercase = 1000       )			->      int:
	_lowercase       :							Dict  	=		0
	_lowercase       :							int  	=		0
	while 1:
		num += 3
		if num >= n:
			break
		total += num
		num += 2
		if num >= n:
			break
		total += num
		num += 1
		if num >= n:
			break
		total += num
		num += 3
		if num >= n:
			break
		total += num
		num += 1
		if num >= n:
			break
		total += num
		num += 2
		if num >= n:
			break
		total += num
		num += 3
		if num >= n:
			break
		total += num
	return total


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