






"""simple docstring"""



import math






class 							__SCREAMING_SNAKE_CASE						:


							def __init__(			self      :						List[str]			,    snake_case      :						str=0							):  # a graph with Node 0,1,...,N-1
													'''simple docstring'''





													A__						:  Tuple		  =  n
													A__						:  Tuple		  =  [
													    [math.inf for j in range(0			,    snake_case							)] for i in range(0			,    snake_case							)
													]  # adjacency matrix for weight
													A__						:  int		  =  [
													    [math.inf for j in range(0			,    snake_case							)] for i in range(0			,    snake_case							)
													]  # dp[i][j] stores minimum distance from i to j


							def 						_UpperCamelCase       (			self      :						str			,    snake_case      :						Optional[Any]			,    snake_case      :						Tuple			,    snake_case      :						Any							):
													'''simple docstring'''





													A__						:  Optional[int]		  =  w


							def 						_UpperCamelCase       (			self      :						Tuple							):
													'''simple docstring'''





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


							def 						_UpperCamelCase       (			self      :						Dict			,    snake_case      :						List[Any]			,    snake_case      :						int							):
													'''simple docstring'''





													return self.dp[u][v]


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



def      _lowerCAmelCase		(							UpperCAmelCase__       :					str,						UpperCAmelCase__       :					List[Any]      )		->List[Any]:
						A__						:  Union[str, Any]		  =  [1]
						for i in range(2,						UpperCAmelCase__      ):
												factorials.append(factorials[-1] * i      )
						assert 0 <= k < factorials[-1] * n, "k out of bounds"

						A__						:  Optional[int]		  =  []
						A__						:  List[str]		  =  list(range(UpperCAmelCase__      )      )

						# Find permutation
						while factorials:
												A__						:  Optional[int]		  =  factorials.pop()
												A__  ,  A__						:  Optional[int]		  =  divmod(UpperCAmelCase__,						UpperCAmelCase__      )
												permutation.append(elements[number]      )
												elements.remove(elements[number]      )
						permutation.append(elements[0]      )

						return permutation


if __name__ == "__main__":
						import doctest

						doctest.testmod()






