
'''simple docstring'''
import math


class       _lowerCAmelCase   :







							'''simple docstring'''

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

							def 	lowercase							(self  ,  UpperCAmelCase  ,  UpperCAmelCase  ,  UpperCAmelCase  )					->       Tuple:
														_snake_case       =  w

							def 	lowercase							(self  )					->       str:
														for k in range(0  ,  self.n  ):
																					for i in range(0  ,  self.n  ):
																												for j in range(0  ,  self.n  ):
																																			_snake_case       =  min(self.dp[i][j]  ,  self.dp[i][k] + self.dp[k][j]  )





							def 	lowercase							(self  ,  UpperCAmelCase  ,  UpperCAmelCase  )					->       List[Any]:
														return self.dp[u][v]


if __name__ == "__main__":
				__lowerCAmelCase												=	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)

'''simple docstring'''
from __future__ import annotations






def  __SCREAMING_SNAKE_CASE				(  _SCREAMING_SNAKE_CASE				):
							_snake_case       =  len(_SCREAMING_SNAKE_CASE				)
							# We need to create solution object to save path.
							_snake_case       =  [[0 for _ in range(_SCREAMING_SNAKE_CASE				)] for _ in range(_SCREAMING_SNAKE_CASE				)]
							_snake_case       =  run_maze(_SCREAMING_SNAKE_CASE							, 0							, 0							, _SCREAMING_SNAKE_CASE				)
							if solved:
														print("""\n""".join(str(_SCREAMING_SNAKE_CASE				) for row in solutions				)				)
							else:
														print("""No solution exists!"""				)
							return solved






def  __SCREAMING_SNAKE_CASE				(  _SCREAMING_SNAKE_CASE							, _SCREAMING_SNAKE_CASE							, _SCREAMING_SNAKE_CASE							, _SCREAMING_SNAKE_CASE				):
							_snake_case       =  len(_SCREAMING_SNAKE_CASE				)
							# Final check point.
							if i == j == (size - 1):
														_snake_case       =  1
														return True

							_snake_case       =  (not i < 0) and (not j < 0)  # Check lower bounds
							_snake_case       =  (i < size) and (j < size)  # Check upper bounds

							if lower_flag and upper_flag:
														# check for already visited and block points.
														_snake_case       =  (not solutions[i][j]) and (not maze[i][j])
														if block_flag:
																					# check visited
																					_snake_case       =  1

																					# check for directions
																					if (
																					    run_maze(_SCREAMING_SNAKE_CASE							, i + 1							, _SCREAMING_SNAKE_CASE							, _SCREAMING_SNAKE_CASE				)
																					    or run_maze(_SCREAMING_SNAKE_CASE							, _SCREAMING_SNAKE_CASE							, j + 1							, _SCREAMING_SNAKE_CASE				)
																					    or run_maze(_SCREAMING_SNAKE_CASE							, i - 1							, _SCREAMING_SNAKE_CASE							, _SCREAMING_SNAKE_CASE				)
																					    or run_maze(_SCREAMING_SNAKE_CASE							, _SCREAMING_SNAKE_CASE							, j - 1							, _SCREAMING_SNAKE_CASE				)
																					):
																												return True

																					_snake_case       =  0
																					return False
							return False


if __name__ == "__main__":
				import doctest

				doctest.testmod()