"""simple docstring"""






from __future__ import annotations

from collections import deque
from enum import Enum
from math import atana, degrees
from sys import maxsize
class     snake_case	(			__UpperCAmelCase    ):




					"""simple docstring"""

					snake_case__       =			1
					snake_case__       =			2
					snake_case__       =			3







					def __repr__(    self       :     int      ):
									return f'''{self.__class__.__name__}.{self.name}'''






def   a_						( lowerCamelCase ,      lowerCamelCase ,      lowerCamelCase	):
				UpperCAmelCase__				,     UpperCAmelCase__					=							point
				return degrees(atana(y - miny ,      x - minx	)	)



def   a_						( lowerCamelCase ,      lowerCamelCase ,      lowerCamelCase	):
				UpperCAmelCase__				,     UpperCAmelCase__					=							starting
				UpperCAmelCase__				,     UpperCAmelCase__					=							via
				UpperCAmelCase__				,     UpperCAmelCase__					=							target
				UpperCAmelCase__					=							degrees(atana(ya - ya ,      xa - xa	)	)
				via_angle %= 3_6_0
				UpperCAmelCase__					=							degrees(atana(ya - ya ,      xa - xa	)	)
				target_angle %= 3_6_0
				# t-
				#  \ \
				#   \ v
				#    \|
				#     s
				# via_angle is always lower than target_angle, if direction is left.
				# If they are same, it means they are on a same line of convex hull.
				if target_angle > via_angle:
								return Direction.left
				elif target_angle == via_angle:
								return Direction.straight
				else:
								return Direction.right




def   a_						( lowerCamelCase	):

				if len(lowerCamelCase	) <= 2:
								# There is no convex hull
								raise ValueError('graham_scan: argument must contain more than 3 points.'	)
				if len(lowerCamelCase	) == 3:
								return points
				# find the lowest and the most left point
				UpperCAmelCase__					=							0
				UpperCAmelCase__				,     UpperCAmelCase__					=							maxsize, maxsize
				for i, point in enumerate(lowerCamelCase	):
								UpperCAmelCase__					=							point[0]
								UpperCAmelCase__					=							point[1]
								if y < miny:
												UpperCAmelCase__					=							y
												UpperCAmelCase__					=							x
												UpperCAmelCase__					=							i
								if y == miny and x < minx:
												UpperCAmelCase__					=							x
												UpperCAmelCase__					=							i

    # remove the lowest and the most left point from points for preparing for sort
				points.pop(lowerCamelCase	)

				UpperCAmelCase__					=							sorted(lowerCamelCase ,      key=lambda lowerCamelCase	: angle_comparer(lowerCamelCase ,      lowerCamelCase ,      lowerCamelCase	)	)
				# This insert actually costs complexity,
				# and you should instead add (minx, miny) into stack later.
				# I'm using insert just for easy understanding.
				sorted_points.insert(0 ,      (minx, miny)	)

				UpperCAmelCase__					=							deque()
				stack.append(sorted_points[0]	)
				stack.append(sorted_points[1]	)
				stack.append(sorted_points[2]	)
				# In any ways, the first 3 points line are towards left.
				# Because we sort them the angle from minx, miny.
				UpperCAmelCase__					=							Direction.left

				for i in range(3 ,      len(lowerCamelCase	)	):
								while True:
												UpperCAmelCase__					=							stack[-2]
												UpperCAmelCase__					=							stack[-1]
												UpperCAmelCase__					=							sorted_points[i]
												UpperCAmelCase__					=							check_direction(lowerCamelCase ,      lowerCamelCase ,      lowerCamelCase	)

												if next_direction == Direction.left:
																UpperCAmelCase__					=							Direction.left
																break
												if next_direction == Direction.straight:
																if current_direction == Direction.left:
																				# We keep current_direction as left.
																				# Because if the straight line keeps as straight,
																				# we want to know if this straight line is towards left.
																				break
																elif current_direction == Direction.right:
																				# If the straight line is towards right,
																				# every previous points on those straigh line is not convex hull.
																				stack.pop()
												if next_direction == Direction.right:
																stack.pop()
								stack.append(sorted_points[i]	)
				return list(lowerCamelCase	)




"""simple docstring"""






from __future__ import annotations
class     snake_case	:




					"""simple docstring"""

					def __init__(    self       :     Tuple   ,lowerCamelCase__       :     int      ):
									UpperCAmelCase__					=							vertices
									UpperCAmelCase__					=							[[0] * vertices for _ in range(lowerCamelCase__      )]







					def 		__lowerCAmelCase						(    self       :     Dict   ,lowerCamelCase__       :     list[int]      ):
									print('Vertex \t Distance from Source'      )
									for vertex in range(self.vertices      ):
													print(lowerCamelCase__   ,'\t\t'   ,distances_from_source[vertex]      )







					def 		__lowerCAmelCase						(    self       :     List[Any]   ,lowerCamelCase__       :     list[int]   ,lowerCamelCase__       :     list[bool]      ):
									UpperCAmelCase__					=							1e7
									UpperCAmelCase__					=							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:
																	UpperCAmelCase__					=							distances_from_source[vertex]
																	UpperCAmelCase__					=							vertex
									return min_index







					def 		__lowerCAmelCase						(    self       :     List[Any]   ,lowerCamelCase__       :     int      ):
									UpperCAmelCase__					=							[int(1e7      )] * self.vertices  # distances from the source
									UpperCAmelCase__					=							0
									UpperCAmelCase__					=							[False] * self.vertices

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

									self.print_solution(lowerCamelCase__      )


if __name__ == "__main__":
						lowerCAmelCase__  :  List[str]											=     Graph(9)
						lowerCAmelCase__  :  Tuple											=     [
						    [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)



