



'''simple docstring'''





import math






class 	lowerCAmelCase_:
		'''simple docstring'''




		def __init__(   self  ,__UpperCAmelCase=0				)   ->		int:  # a graph with Node 0,1,...,N-1
						lowerCAmelCase__			:  List[str]											= n
						lowerCAmelCase__			:  int											= [
						    [math.inf for j in range(0  ,_UpperCAmelCase				)] for i in range(0  ,_UpperCAmelCase				)
						]  # adjacency matrix for weight
						lowerCAmelCase__			:  List[str]											= [
						    [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 							UpperCAmelCase_     (   self  ,__UpperCAmelCase  ,__UpperCAmelCase  ,__UpperCAmelCase				)   ->		Union[str, Any]:
						lowerCAmelCase__			:  Optional[Any]											= w




		def 							UpperCAmelCase_     (   self				)   ->		Optional[Any]:
						for k in range(0  ,self.n				):
										for i in range(0  ,self.n				):
														for j in range(0  ,self.n				):
																		lowerCAmelCase__			:  Union[str, Any]											= min(self.dp[i][j]  ,self.dp[i][k] + self.dp[k][j]				)






		def 							UpperCAmelCase_     (   self  ,__UpperCAmelCase  ,__UpperCAmelCase				)   ->		Optional[int]:
						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'''





class 	lowerCAmelCase_:
  '''simple docstring'''




  def __init__(   self  ,__UpperCAmelCase				)   ->		Tuple:
      lowerCAmelCase__			:  Union[str, Any]											= n
      lowerCAmelCase__			:  int											= [None] * self.n
      lowerCAmelCase__			:  Union[str, Any]											= 0  # index of the first element
      lowerCAmelCase__			:  Union[str, Any]											= 0
      lowerCAmelCase__			:  Union[str, Any]											= 0




  def __len__(   self				)   ->		int:
      return self.size




  def 							UpperCAmelCase_     (   self				)   ->		bool:
      return self.size == 0




  def 							UpperCAmelCase_     (   self				)   ->		Optional[Any]:
      return False if self.is_empty() else self.array[self.front]




  def 							UpperCAmelCase_     (   self  ,__UpperCAmelCase				)   ->		Union[str, Any]:
      if self.size >= self.n:
          raise Exception("""QUEUE IS FULL"""				)

      lowerCAmelCase__			:  str											= data
      lowerCAmelCase__			:  List[str]											= (self.rear + 1) % self.n
      self.size += 1
      return self






  def 							UpperCAmelCase_     (   self				)   ->		int:
      if self.size == 0:
          raise Exception("""UNDERFLOW"""				)

      lowerCAmelCase__			:  int											= self.array[self.front]
      lowerCAmelCase__			:  Optional[Any]											= None
      lowerCAmelCase__			:  int											= (self.front + 1) % self.n
      self.size -= 1
      return temp


