

def 	_snake_case		(    SCREAMING_SNAKE_CASE		,							SCREAMING_SNAKE_CASE		,							SCREAMING_SNAKE_CASE				)       ->      int:

     """simple docstring"""







     if len(SCREAMING_SNAKE_CASE				) != len(SCREAMING_SNAKE_CASE				):
          raise ValueError("The length of profit and weight must be same."				)
     if max_weight <= 0:
          raise ValueError("max_weight must greater than zero."				)
     if any(p < 0 for p in profit				):
          raise ValueError("Profit can not be negative."				)
     if any(w < 0 for w in weight				):
          raise ValueError("Weight can not be negative."				)

     # List created to store profit gained for the 1kg in case of each weight
     # respectively.  Calculate and append profit/weight for each element.
     _lowerCAmelCase   :					Optional[Any]        =    [p / w for p, w in zip(SCREAMING_SNAKE_CASE		,							SCREAMING_SNAKE_CASE				)]

     # Creating a copy of the list and sorting profit/weight in ascending order
     _lowerCAmelCase   :					Dict        =    sorted(SCREAMING_SNAKE_CASE				)

     # declaring useful variables
     _lowerCAmelCase   :					Optional[int]        =    len(SCREAMING_SNAKE_CASE				)
     _lowerCAmelCase   :					Any        =    0
     _lowerCAmelCase   :					Optional[Any]        =    0
     _lowerCAmelCase   :					Tuple        =    0

     # loop till the total weight do not reach max limit e.g. 15 kg and till i<length
     while limit <= max_weight and i < length:
          # flag value for encountered greatest element in sorted_profit_by_weight
          _lowerCAmelCase   :					Any        =    sorted_profit_by_weight[length - i - 1]
          _lowerCAmelCase   :					Optional[int]        =    profit_by_weight.index(SCREAMING_SNAKE_CASE				)
          _lowerCAmelCase   :					str        =    -1

          # check if the weight encountered is less than the total weight
          # encountered before.
          if max_weight - limit >= weight[index]:
               limit += weight[index]
               # Adding profit gained for the given weight 1 ===
               # weight[index]/weight[index]
               gain += 1 * profit[index]
          else:
               # Since the weight encountered is greater than limit, therefore take the
               # required number of remaining kgs and calculate profit for it.
               # weight remaining / weight[index]
               gain += (max_weight - limit) / weight[index] * profit[index]
               break
          i += 1
     return gain


if __name__ == "__main__":
  print(
      'Input profits, weights, and then max_weight (all positive ints) separated by '
      'spaces.'
  )

  __UpperCAmelCase    				=     [int(x) for x in input('Input profits separated by spaces: ').split()]
  __UpperCAmelCase    				=     [int(x) for x in input('Input weights separated by spaces: ').split()]
  __UpperCAmelCase    				=     int(input('Max weight allowed: '))

  # Function Call
  calc_profit(profit, weight, max_weight)









from __future__ import annotations







def 	_snake_case		(    SCREAMING_SNAKE_CASE		,							SCREAMING_SNAKE_CASE				)       ->      List[Any]:

     """simple docstring"""







     print(f'''Vertex\tShortest Distance from vertex {src}'''				)
     for i, d in enumerate(SCREAMING_SNAKE_CASE				):
          print(f'''{i}\t\t{d}'''				)







def 	_snake_case		(    SCREAMING_SNAKE_CASE		,							SCREAMING_SNAKE_CASE		,							SCREAMING_SNAKE_CASE				)       ->      Tuple:

     """simple docstring"""







     for j in range(SCREAMING_SNAKE_CASE				):
          _lowerCAmelCase      ,			_lowerCAmelCase      ,			_lowerCAmelCase   :					Any        =    (graph[j][k] for k in ["src", "dst", "weight"])
          if distance[u] != float("inf"				) and distance[u] + w < distance[v]:
               return True
     return False







def 	_snake_case		(    SCREAMING_SNAKE_CASE		,							SCREAMING_SNAKE_CASE		,							SCREAMING_SNAKE_CASE		,							SCREAMING_SNAKE_CASE				)       ->      list[float]:

     """simple docstring"""







     _lowerCAmelCase   :					Tuple        =    [float("inf"				)] * vertex_count
     _lowerCAmelCase   :					int        =    0.0

     for _ in range(vertex_count - 1				):
          for j in range(SCREAMING_SNAKE_CASE				):
               _lowerCAmelCase      ,			_lowerCAmelCase      ,			_lowerCAmelCase   :					int        =    (graph[j][k] for k in ["src", "dst", "weight"])

               if distance[u] != float("inf"				) and distance[u] + w < distance[v]:
                    _lowerCAmelCase   :					List[str]        =    distance[u] + w

     _lowerCAmelCase   :					int        =    check_negative_cycle(SCREAMING_SNAKE_CASE		,							SCREAMING_SNAKE_CASE		,							SCREAMING_SNAKE_CASE				)
     if negative_cycle_exists:
          raise Exception("Negative cycle found"				)

     return distance


if __name__ == "__main__":
  import doctest

  doctest.testmod()

  __UpperCAmelCase    				=     int(input('Enter number of vertices: ').strip())
  __UpperCAmelCase    				=     int(input('Enter number of edges: ').strip())

  __UpperCAmelCase    				=     [{} for _ in range(E)]

  for i in range(E):
    print('Edge ', i + 1)
    __UpperCAmelCase				,__UpperCAmelCase				,__UpperCAmelCase    				=     (
        int(x)
        for x in input('Enter source, destination, weight: ').strip().split(' ')
    )
    __UpperCAmelCase    				=     {'src': src, 'dst': dest, 'weight': weight}

  __UpperCAmelCase    				=     int(input('\nEnter shortest path source:').strip())
  __UpperCAmelCase    				=     bellman_ford(graph, V, E, source)
  print_distance(shortest_distance, 0)






