

import unittest
from dataclasses import dataclass
from typing import Optional

from transformers.utils import ModelOutput






@dataclass
class _UpperCamelCase							(							UpperCamelCase_				):
			'''simple docstring'''







			lowerCamelCase__          =42
			lowerCamelCase__          =None
			lowerCamelCase__          =None






class _UpperCamelCase							(							unittest.TestCase				):
			'''simple docstring'''







			def 							__UpperCamelCase	(     self							:	str		)							->    Optional[Any]:

				"""simple docstring"""

				SCREAMING_SNAKE_CASE				: List[Any]			       =    ModelOutputTest(a=30		)
				self.assertEqual(x.a , 30		)
				self.assertIsNone(x.b		)
				self.assertIsNone(x.c		)
				with self.assertRaises(lowercase_		):
					SCREAMING_SNAKE_CASE				: Any			       =    x.d
			def 							__UpperCamelCase	(     self							:	List[Any]		)							->    str:

				"""simple docstring"""

				SCREAMING_SNAKE_CASE				: Tuple			       =    ModelOutputTest(a=30 , b=10		)
				self.assertEqual(x[0] , 30		)
				self.assertEqual(x[1] , 10		)
				self.assertEqual(x[:2] , (30, 10)		)
				self.assertEqual(x[:] , (30, 10)		)

				SCREAMING_SNAKE_CASE				: int			       =    ModelOutputTest(a=30 , c=10		)
				self.assertEqual(x[0] , 30		)
				self.assertEqual(x[1] , 10		)
				self.assertEqual(x[:2] , (30, 10)		)
				self.assertEqual(x[:] , (30, 10)		)
			def 							__UpperCamelCase	(     self							:	Tuple		)							->    Dict:

				"""simple docstring"""

				SCREAMING_SNAKE_CASE				: Optional[Any]			       =    ModelOutputTest(a=30 , b=10		)
				self.assertEqual(x["a"] , 30		)
				self.assertEqual(x["b"] , 10		)
				with self.assertRaises(lowercase_		):
					SCREAMING_SNAKE_CASE				: Union[str, Any]			       =    x['c']

				SCREAMING_SNAKE_CASE				: Union[str, Any]			       =    ModelOutputTest(a=30 , c=10		)
				self.assertEqual(x["a"] , 30		)
				self.assertEqual(x["c"] , 10		)
				with self.assertRaises(lowercase_		):
					SCREAMING_SNAKE_CASE				: int			       =    x['b']
			def 							__UpperCamelCase	(     self							:	List[str]		)							->    Union[str, Any]:

				"""simple docstring"""

				SCREAMING_SNAKE_CASE				: Optional[int]			       =    ModelOutputTest(a=30		)
				self.assertEqual(list(x.keys()		) , ["a"]		)
				self.assertEqual(list(x.values()		) , [30]		)
				self.assertEqual(list(x.items()		) , [("a", 30)]		)
				self.assertEqual(list(lowercase_		) , ["a"]		)

				SCREAMING_SNAKE_CASE				: List[Any]			       =    ModelOutputTest(a=30 , b=10		)
				self.assertEqual(list(x.keys()		) , ["a", "b"]		)
				self.assertEqual(list(x.values()		) , [30, 10]		)
				self.assertEqual(list(x.items()		) , [("a", 30), ("b", 10)]		)
				self.assertEqual(list(lowercase_		) , ["a", "b"]		)

				SCREAMING_SNAKE_CASE				: Optional[Any]			       =    ModelOutputTest(a=30 , c=10		)
				self.assertEqual(list(x.keys()		) , ["a", "c"]		)
				self.assertEqual(list(x.values()		) , [30, 10]		)
				self.assertEqual(list(x.items()		) , [("a", 30), ("c", 10)]		)
				self.assertEqual(list(lowercase_		) , ["a", "c"]		)

				with self.assertRaises(lowercase_		):
					SCREAMING_SNAKE_CASE				: List[str]			       =    x.update({"d": 20}		)
				with self.assertRaises(lowercase_		):
					del x["a"]
				with self.assertRaises(lowercase_		):
					SCREAMING_SNAKE_CASE				: Tuple			       =    x.pop("a"		)
				with self.assertRaises(lowercase_		):
					SCREAMING_SNAKE_CASE				: Optional[int]			       =    x.setdefault("d" , 32		)
			def 							__UpperCamelCase	(     self							:	Dict		)							->    Dict:

				"""simple docstring"""

				SCREAMING_SNAKE_CASE				: Union[str, Any]			       =    ModelOutputTest(a=30		)
				SCREAMING_SNAKE_CASE				: List[str]			       =    10
				self.assertEqual(x.a , 10		)
				self.assertEqual(x["a"] , 10		)
			def 							__UpperCamelCase	(     self							:	List[str]		)							->    int:

				"""simple docstring"""

				SCREAMING_SNAKE_CASE				: List[str]			       =    ModelOutputTest(a=30		)
				SCREAMING_SNAKE_CASE				: Union[str, Any]			       =    10
				self.assertEqual(x.a , 10		)
				self.assertEqual(x["a"] , 10		)
			def 							__UpperCamelCase	(     self							:	Union[str, Any]		)							->    Optional[int]:

				"""simple docstring"""

				SCREAMING_SNAKE_CASE				: Optional[Any]			       =    ModelOutputTest({"a": 30, "b": 10}		)
				self.assertEqual(list(x.keys()		) , ["a", "b"]		)
				self.assertEqual(x.a , 30		)
				self.assertEqual(x.b , 10		)






			def 							__UpperCamelCase	(     self							:	Any		)							->    Optional[int]:

				"""simple docstring"""

				SCREAMING_SNAKE_CASE				: List[Any]			       =    ModelOutputTest([("a", 30), ("b", 10)]		)
				self.assertEqual(list(x.keys()		) , ["a", "b"]		)
				self.assertEqual(x.a , 30		)
				self.assertEqual(x.b , 10		)

				with self.assertRaises(lowercase_		):
					SCREAMING_SNAKE_CASE				: Optional[Any]			       =    ModelOutputTest([("a", 30), (10, 10)]		)

				SCREAMING_SNAKE_CASE				: Tuple			       =    ModelOutputTest(a=(30, 30)		)
				self.assertEqual(list(x.keys()		) , ["a"]		)
				self.assertEqual(x.a , (30, 30)		)


from __future__ import annotations






class _UpperCamelCase							:
			'''simple docstring'''







			def __init__(     self							:	List[Any] , a							:	int		)							->    None:

				"""simple docstring"""

				SCREAMING_SNAKE_CASE				: List[str]			       =    vertices
				SCREAMING_SNAKE_CASE				: Tuple			       =    [[0] * vertices for _ in range(a		)]
			def 							__UpperCamelCase	(     self							:	Dict , a							:	list[int]		)							->    None:

				"""simple docstring"""

				print("Vertex \t Distance from Source"		)
				for vertex in range(self.vertices		):
					print(a , "\t\t" , distances_from_source[vertex]		)
			def 							__UpperCamelCase	(     self							:	Tuple , a							:	list[int] , a							:	list[bool]		)							->    int:

				"""simple docstring"""

				SCREAMING_SNAKE_CASE				: Dict			       =    1e7
				SCREAMING_SNAKE_CASE				: 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:
						SCREAMING_SNAKE_CASE				: Optional[int]			       =    distances_from_source[vertex]
						SCREAMING_SNAKE_CASE				: Optional[Any]			       =    vertex
				return min_index






			def 							__UpperCamelCase	(     self							:	Any , a							:	int		)							->    None:

				"""simple docstring"""

				SCREAMING_SNAKE_CASE				: List[str]			       =    [int(1e7		)] * self.vertices  # distances from the source
				SCREAMING_SNAKE_CASE				: Tuple			       =    0
				SCREAMING_SNAKE_CASE				: List[Any]			       =    [False] * self.vertices

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

				self.print_solution(a		)


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