



class 	UpperCAmelCase	:


 '''simple docstring'''




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



      """simple docstring"""







      a_       		=""
      a_       		=""
      a_       		=[]




 def       lowercase_  (   self							,  lowerCAmelCase_							,  lowerCAmelCase_) ->      Optional[int]:



      """simple docstring"""







      if m == -1:
           return n + 1
      elif n == -1:
           return m + 1
      elif self.dp[m][n] > -1:
           return self.dp[m][n]
      else:
           if self.worda[m] == self.worda[n]:
                a_       		=self.__min_dist_top_down_dp(m - 1							,  n - 1)
           else:
                a_       		=self.__min_dist_top_down_dp(__UpperCamelCase							,  n - 1)
                a_       		=self.__min_dist_top_down_dp(m - 1							,  __UpperCamelCase)
                a_       		=self.__min_dist_top_down_dp(m - 1							,  n - 1)
                a_       		=1 + min(__UpperCamelCase							,  __UpperCamelCase							,  __UpperCamelCase)

           return self.dp[m][n]




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



      """simple docstring"""







      a_       		=worda
      a_       		=worda
      a_       		=[[-1 for _ in range(len(__UpperCamelCase))] for _ in range(len(__UpperCamelCase))]

      return self.__min_dist_top_down_dp(len(__UpperCamelCase) - 1							,  len(__UpperCamelCase) - 1)




 def       lowercase_  (   self							,  lowerCAmelCase_							,  lowerCAmelCase_) ->      List[Any]:



      """simple docstring"""







      a_       		=worda
      a_       		=worda
      a_       		=len(__UpperCamelCase)
      a_       		=len(__UpperCamelCase)
      a_       		=[[0 for _ in range(n + 1)] for _ in range(m + 1)]

      for i in range(m + 1):
           for j in range(n + 1):
                if i == 0:  # first string is empty
                     a_       		=j
                elif j == 0:  # second string is empty
                     a_       		=i
                elif worda[i - 1] == worda[j - 1]:  # last characters are equal
                     a_       		=self.dp[i - 1][j - 1]
                else:
                     a_       		=self.dp[i][j - 1]
                     a_       		=self.dp[i - 1][j]
                     a_       		=self.dp[i - 1][j - 1]
                     a_       		=1 + min(__UpperCamelCase							,  __UpperCamelCase							,  __UpperCamelCase)
      return self.dp[m][n]


if __name__ == "__main__":
  lowercase							       =			EditDistance()

  print('''****************** Testing Edit Distance DP Algorithm ******************''')
  print()

  lowercase							       =			input('''Enter the first string: ''').strip()
  lowercase							       =			input('''Enter the second string: ''').strip()

  print()
  print(F"""The minimum edit distance is: {solver.min_dist_top_down(Sa, Sa)}""")
  print(F"""The minimum edit distance is: {solver.min_dist_bottom_up(Sa, Sa)}""")
  print()
  print('''*************** End of Testing Edit Distance DP Algorithm ***************''')







'''simple docstring'''


from __future__ import annotations






def  UpperCAmelCase_       (		lowercase__       ,	lowercase__       ):


     '''simple docstring'''







     print(F"""Vertex\tShortest Distance from vertex {src}"""       )
     for i, d in enumerate(lowercase__       ):
          print(F"""{i}\t\t{d}"""       )






def  UpperCAmelCase_       (		lowercase__       ,	lowercase__       ,	lowercase__       ):


     '''simple docstring'''







     for j in range(lowercase__       ):
          a_		,						a_		,						a_       		=(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  UpperCAmelCase_       (		lowercase__       ,	lowercase__       ,	lowercase__       ,	lowercase__       ):


     '''simple docstring'''







     a_       		=[float("inf"       )] * vertex_count
     a_       		=0.0

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

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

     a_       		=check_negative_cycle(lowercase__       ,	lowercase__       ,	lowercase__       )
     if negative_cycle_exists:
          raise Exception("Negative cycle found"       )

     return distance


if __name__ == "__main__":
  import doctest

  doctest.testmod()

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

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

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

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


