

from __future__ import annotations
class 		SCREAMING_SNAKE_CASE__					:







						"""simple docstring"""




						def __init__(				self , __UpperCamelCase    )							->	None:




									'''simple docstring'''


									__UpperCamelCase    :    Union[str, Any]								=      vertices
									__UpperCamelCase    :    Dict								=      [[0] * vertices for _ in range(__UpperCamelCase    )]

						def __lowerCamelCase					(				self , __UpperCamelCase    )							->	None:




									'''simple docstring'''


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

						def __lowerCamelCase					(				self , __UpperCamelCase , __UpperCamelCase    )							->	int:




									'''simple docstring'''


									__UpperCamelCase    :    Union[str, Any]								=      1E7
									__UpperCamelCase    :    int								=      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    :    Union[str, Any]								=      distances_from_source[vertex]
															__UpperCamelCase    :    Optional[int]								=      vertex
									return min_index




						def __lowerCamelCase					(				self , __UpperCamelCase    )							->	None:




									'''simple docstring'''


									__UpperCamelCase    :    Dict								=      [int(1E7    )] * self.vertices  # distances from the source
									__UpperCamelCase    :    Union[str, Any]								=      0
									__UpperCamelCase    :    int								=      [False] * self.vertices

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

									self.print_solution(__UpperCamelCase    )


if __name__ == "__main__":
					lowercase     :       int        =       Graph(9)
					lowercase     :       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)


lowercase     :       dict[str, float]        =       {
    "kilogram": 1,
    "gram": pow(10, 3),
    "milligram": pow(10, 6),
    "metric-ton": pow(10, -3),
    "long-ton": 0.0009842073,
    "short-ton": 0.0011023122,
    "pound": 2.2046244202,
    "stone": 0.1574731728,
    "ounce": 35.273990723,
    "carrat": 5000,
    "atomic-mass-unit": 6.0_22_13_66_52E26,
}

lowercase     :       dict[str, float]        =       {
    "kilogram": 1,
    "gram": pow(10, -3),
    "milligram": pow(10, -6),
    "metric-ton": pow(10, 3),
    "long-ton": 1016.04608,
    "short-ton": 907.184,
    "pound": 0.453592,
    "stone": 6.35029,
    "ounce": 0.0283495,
    "carrat": 0.0002,
    "atomic-mass-unit": 1.6_60_54_01_99E-27,
}







def  UpperCAmelCase_   (_lowerCAmelCase :		str     ,			_lowerCAmelCase :		str     ,			_lowerCAmelCase :		float		):
			if to_type not in KILOGRAM_CHART or from_type not in WEIGHT_TYPE_CHART:
						__UpperCamelCase    :    Dict								=      (
						    F'''Invalid \'from_type\' or \'to_type\' value: {from_type!r}, {to_type!r}\n'''
						    F'''Supported values are: {", ".join(_lowerCAmelCase		)}'''
						)
						raise ValueError(_lowerCAmelCase		)
			return value * KILOGRAM_CHART[to_type] * WEIGHT_TYPE_CHART[from_type]


if __name__ == "__main__":
					import doctest

					doctest.testmod()