
import math





class 							UpperCAmelCase      :




	'''simple docstring'''





	def __init__(       self					: Optional[int]							,A					: Dict=0 ):  # a graph with Node 0,1,...,N-1
					__A   			= n
					__A   			= [
					    [math.inf for j in range(0							,A )] for i in range(0							,A )
					]  # adjacency matrix for weight
					__A   			= [
					    [math.inf for j in range(0							,A )] for i in range(0							,A )
					]  # dp[i][j] stores minimum distance from i to j






	def 				UpperCamelCase_  (       self					: List[str]							,A					: Tuple							,A					: Union[str, Any]							,A					: Optional[int] ):
					__A   			= w






	def 				UpperCamelCase_  (       self					: int ):
					for k in range(0							,self.n ):
									for i in range(0							,self.n ):
													for j in range(0							,self.n ):
																	__A   			= min(self.dp[i][j]							,self.dp[i][k] + self.dp[k][j] )







	def 				UpperCamelCase_  (       self					: Optional[int]							,A					: str							,A					: Union[str, Any] ):
					return self.dp[u][v]


if __name__ == "__main__":
					SCREAMING_SNAKE_CASE							:Optional[int]							 =				Graph(5)
					graph.add_edge(0, 2, 9)
					graph.add_edge(0, 4, 10)
					graph.add_edge(1, 3, 5)
					graph.add_edge(2, 3, 7)
					graph.add_edge(3, 0, 10)
					graph.add_edge(3, 1, 2)
					graph.add_edge(3, 2, 1)
					graph.add_edge(3, 4, 6)
					graph.add_edge(4, 1, 3)
					graph.add_edge(4, 2, 4)
					graph.add_edge(4, 3, 9)
					graph.floyd_warshall()
					graph.show_min(1, 4)
					graph.show_min(0, 3)







# This code is adapted from OpenAI's release
# https://github.com/openai/human-eval/blob/master/human_eval/execution.py

import contextlib
import faulthandler
import io
import multiprocessing
import os
import platform
import signal
import tempfile







def    __lowerCamelCase					(							__a   :List[str]    ,     __a   :List[Any]    ,     __a   :Union[str, Any]    ,     __a   :List[Any]    )		->				Dict:






		"""simple docstring"""

		A__        =   multiprocessing.Manager()
		A__        =   manager.list()

		A__        =   multiprocessing.Process(target=__a    ,     args=(check_program, result, timeout)    )
		p.start()
		p.join(timeout=timeout + 1    )
		if p.is_alive():
				p.kill()

		if not result:
				result.append("""timed out"""    )

		return {
		    "task_id": task_id,
		    "passed": result[0] == "passed",
		    "result": result[0],
		    "completion_id": completion_id,
		}







def    __lowerCamelCase					(							__a   :Optional[Any]    ,     __a   :Any    ,     __a   :List[Any]    )		->				Union[str, Any]:






		"""simple docstring"""

		with create_tempdir():
				# These system calls are needed when cleaning up tempdir.
				import os
				import shutil

				A__        =   shutil.rmtree
				A__        =   os.rmdir
				A__        =   os.chdir

				# Disable functionalities that can make destructive changes to the test.
				reliability_guard()

				# Run program.
				try:
						A__        =   {}
						with swallow_io():
								with time_limit(__a    ):
										exec(__a    ,     __a    )
						result.append("""passed"""    )
				except TimeoutException:
						result.append("""timed out"""    )
				except BaseException as e:
						result.append(F'failed: {e}'    )

				# Needed for cleaning up.
				A__        =   rmtree
				A__        =   rmdir
				A__        =   chdir







@contextlib.contextmanager
def    __lowerCamelCase					(							__a   :List[str]    )		->				Dict:






		"""simple docstring"""

		def signal_handler(__a   :List[Any]    ,     __a   :Optional[Any]    ):
				raise TimeoutException("""Timed out!"""    )

		signal.setitimer(signal.ITIMER_REAL    ,     __a    )
		signal.signal(signal.SIGALRM    ,     __a    )
		try:
				yield
		finally:
				signal.setitimer(signal.ITIMER_REAL    ,     0    )







@contextlib.contextmanager
def    __lowerCamelCase					(							)		->				Union[str, Any]:






		"""simple docstring"""

		A__        =   WriteOnlyStringIO()
		with contextlib.redirect_stdout(__a    ):
				with contextlib.redirect_stderr(__a    ):
						with redirect_stdin(__a    ):
								yield







@contextlib.contextmanager
def    __lowerCamelCase					(							)		->				Dict:






		"""simple docstring"""

		with tempfile.TemporaryDirectory() as dirname:
				with chdir(__a    ):
						yield dirname


class   A			(SCREAMING_SNAKE_CASE    ):
			'''simple docstring'''




			pass


class   A			(io.StringIO    ):
			'''simple docstring'''




			def    a_       (			self   :    Any							,	*__lowerCAmelCase   :    List[str]							,	**__lowerCAmelCase   :    str   )	->	Dict:







					"""simple docstring"""






					raise OSError






			def    a_       (			self   :    Optional[Any]							,	*__lowerCAmelCase   :    Any							,	**__lowerCAmelCase   :    Optional[int]   )	->	str:







					"""simple docstring"""






					raise OSError






			def    a_       (			self   :    Optional[Any]							,	*__lowerCAmelCase   :    Any							,	**__lowerCAmelCase   :    Any   )	->	int:







					"""simple docstring"""






					raise OSError







			def    a_       (			self   :    str							,	*__lowerCAmelCase   :    Any							,	**__lowerCAmelCase   :    Union[str, Any]   )	->	int:







					"""simple docstring"""






					return False


class   A			(contextlib._RedirectStream    ):  # type: ignore
			'''simple docstring'''




			__lowerCamelCase	:       Union[str, Any]							=    '''stdin'''







@contextlib.contextmanager
def    __lowerCamelCase					(							__a   :Union[str, Any]    )		->				List[str]:






		"""simple docstring"""

		if root == ".":
				yield
				return
		A__        =   os.getcwd()
		os.chdir(__a    )
		try:
				yield
		except BaseException as exc:
				raise exc
		finally:
				os.chdir(__a    )







def    __lowerCamelCase					(							__a   :Union[str, Any]=None    )		->				Dict:






		"""simple docstring"""

		if maximum_memory_bytes is not None:
				import resource

				resource.setrlimit(resource.RLIMIT_AS    ,     (maximum_memory_bytes, maximum_memory_bytes)    )
				resource.setrlimit(resource.RLIMIT_DATA    ,     (maximum_memory_bytes, maximum_memory_bytes)    )
				if not platform.uname().system == "Darwin":
						resource.setrlimit(resource.RLIMIT_STACK    ,     (maximum_memory_bytes, maximum_memory_bytes)    )

		faulthandler.disable()

		import builtins

		A__        =   None
		A__        =   None

		import os

		A__        =   """1"""

		A__        =   None
		A__        =   None
		A__        =   None
		A__        =   None
		A__        =   None
		A__        =   None
		A__        =   None
		A__        =   None
		A__        =   None
		A__        =   None
		A__        =   None
		A__        =   None
		A__        =   None
		A__        =   None
		A__        =   None
		A__        =   None
		A__        =   None
		A__        =   None
		A__        =   None
		A__        =   None
		A__        =   None
		A__        =   None
		A__        =   None
		A__        =   None
		A__        =   None
		A__        =   None
		A__        =   None

		import shutil

		A__        =   None
		A__        =   None
		A__        =   None

		import subprocess

		A__        =   None  # type: ignore

		A__        =   None

		import sys

		A__        =   None
		A__        =   None
		A__        =   None
		A__        =   None
		A__        =   None



