




import math





class 					__lowerCamelCase			:




    """simple docstring"""

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


    def   a (			self	:	Optional[Any]  ,      SCREAMING_SNAKE_CASE__	:	str  ,      SCREAMING_SNAKE_CASE__	:	Any  ,      SCREAMING_SNAKE_CASE__	:	Tuple  ) ->			List[Any]:
         lowerCAmelCase__            =					w


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


    def   a (			self	:	Tuple  ,      SCREAMING_SNAKE_CASE__	:	List[str]  ,      SCREAMING_SNAKE_CASE__	:	Tuple  ) ->			Dict:
         return self.dp[u][v]


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






       def __init__(	self			:				Any							,   UpperCAmelCase_			:				List[str]							,   UpperCAmelCase_			:				Optional[Any]							,   UpperCAmelCase_			:				Optional[Any]      )->	Optional[int]:







              """simple docstring"""
              UpperCamelCase       			=		name
              UpperCamelCase       			=		value
              UpperCamelCase       			=		weight






       def __repr__(	self			:				int      )->	Any:







              """simple docstring"""
              return f"{self.__class__.__name__}({self.name}, {self.value}, {self.weight})"






       def 						_SCREAMING_SNAKE_CASE							(	self			:				int      )->	Union[str, Any]:







              """simple docstring"""
              return self.value






       def 						_SCREAMING_SNAKE_CASE							(	self			:				Optional[int]      )->	int:







              """simple docstring"""
              return self.name






       def 						_SCREAMING_SNAKE_CASE							(	self			:				Tuple      )->	List[Any]:







              """simple docstring"""
              return self.weight






       def 						_SCREAMING_SNAKE_CASE							(	self			:				Any      )->	Union[str, Any]:







              """simple docstring"""
              return self.value / self.weight





def 						lowerCamelCase__      (				UpperCAmelCase_		,   UpperCAmelCase_		,   UpperCAmelCase_					)->				Union[str, Any]:







       """simple docstring"""
       UpperCamelCase       			=		[]
       for i in range(len(UpperCAmelCase_					)					):
              menu.append(Things(name[i]		,   value[i]		,   weight[i]					)					)
       return menu



def 						lowerCamelCase__      (				UpperCAmelCase_		,   UpperCAmelCase_		,   UpperCAmelCase_					)->				Dict:







       """simple docstring"""
       UpperCamelCase       			=		sorted(UpperCAmelCase_		,   key=UpperCAmelCase_		,   reverse=UpperCAmelCase_					)
       UpperCamelCase       			=		[]
       UpperCamelCase			,							UpperCamelCase       			=		0.0, 0.0
       for i in range(len(UpperCAmelCase_					)					):
              if (total_cost + items_copy[i].get_weight()) <= max_cost:
                     result.append(items_copy[i]					)
                     total_cost += items_copy[i].get_weight()
                     total_value += items_copy[i].get_value()
       return (result, total_value)



def 						lowerCamelCase__      (				)->				Dict:







       """simple docstring"""


if __name__ == "__main__":
      import doctest

      doctest.testmod()





