



from __future__ import annotations







def    _snake_case (       __snake_case					,  __snake_case    )     ->     Tuple:






      '''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 (       __snake_case					,  __snake_case					,  __snake_case    )     ->     List[Any]:






      '''simple docstring'''







      for j in range(SCREAMING_SNAKE_CASE_    ):
            UpperCAmelCase_      ,      UpperCAmelCase_      ,      UpperCAmelCase_  :	Tuple				      =		(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 (       __snake_case					,  __snake_case					,  __snake_case					,  __snake_case    )     ->     list[float]:






      '''simple docstring'''







      UpperCAmelCase_  :	List[Any]				      =		[float("inf"    )] * vertex_count
      UpperCAmelCase_  :	Dict				      =		0.0

      for _ in range(vertex_count - 1    ):
            for j in range(SCREAMING_SNAKE_CASE_    ):
                  UpperCAmelCase_      ,      UpperCAmelCase_      ,      UpperCAmelCase_  :	List[str]				      =		(graph[j][k] for k in ["src", "dst", "weight"])

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

      UpperCAmelCase_  :	Optional[Any]				      =		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()

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

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

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

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






from __future__ import annotations

from collections import deque
from collections.abc import Iterator
from dataclasses import dataclass


@dataclass
class   snake_case_ :




       """simple docstring"""






       _lowerCamelCase			    =				42
       _lowerCamelCase			    =				42


class   snake_case_ :




       """simple docstring"""






       def __init__(     self     ,lowercase):

             """simple docstring"""





             UpperCAmelCase_  :	list[list[Edge]]				      =		[[] for _ in range(lowercase)]
             UpperCAmelCase_  :	str				      =		size



       def __getitem__(     self     ,lowercase):

             """simple docstring"""





             return iter(self._graph[vertex])



       @property
       def  A_   (     self):

             """simple docstring"""





             return self._size



       def  A_   (     self     ,lowercase     ,lowercase     ,lowercase):

             """simple docstring"""





             if weight not in (0, 1):
                   raise ValueError("Edge weight must be either 0 or 1.")

             if to_vertex < 0 or to_vertex >= self.size:
                   raise ValueError("Vertex indexes must be in [0; size).")

             self._graph[from_vertex].append(Edge(lowercase     ,lowercase))



       def  A_   (     self     ,lowercase     ,lowercase):

             """simple docstring"""





             UpperCAmelCase_  :	int				      =		deque([start_vertex])
             UpperCAmelCase_  :	list[int | None]				      =		[None] * self.size
             UpperCAmelCase_  :	Dict				      =		0

             while queue:
                   UpperCAmelCase_  :	List[Any]				      =		queue.popleft()
                   UpperCAmelCase_  :	Any				      =		distances[current_vertex]
                   if current_distance is None:
                         continue

                   for edge in self[current_vertex]:
                         UpperCAmelCase_  :	Tuple				      =		current_distance + edge.weight
                         UpperCAmelCase_  :	Optional[Any]				      =		distances[edge.destination_vertex]
                         if (
                             isinstance(lowercase     ,lowercase)
                             and new_distance >= dest_vertex_distance
                         ):
                               continue
                         UpperCAmelCase_  :	Tuple				      =		new_distance
                         if edge.weight == 0:
                               queue.appendleft(edge.destination_vertex)
                         else:
                               queue.append(edge.destination_vertex)

             if distances[finish_vertex] is None:
                   raise ValueError("No path from start_vertex to finish_vertex.")

             return distances[finish_vertex]


if __name__ == "__main__":
   import doctest

   doctest.testmod()
