





'''simple docstring'''


from __future__ import annotations


def 	__a(SCREAMING_SNAKE_CASE_  :					list[float]		,       SCREAMING_SNAKE_CASE_  :					Union[str, 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 	__a(SCREAMING_SNAKE_CASE_  :					list[dict[str, int]]		,       SCREAMING_SNAKE_CASE_  :					list[float]		,       SCREAMING_SNAKE_CASE_  :					int    ):



    '''simple docstring'''





    for j in range(SCREAMING_SNAKE_CASE_    ):
        _lowerCAmelCase			,			_lowerCAmelCase			,			_lowerCAmelCase				=      (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 	__a(SCREAMING_SNAKE_CASE_  :					list[dict[str, int]]		,       SCREAMING_SNAKE_CASE_  :					int		,       SCREAMING_SNAKE_CASE_  :					int		,       SCREAMING_SNAKE_CASE_  :					int    ):



    '''simple docstring'''





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

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

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

    _lowerCAmelCase				=      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()

       _SCREAMING_SNAKE_CASE	 =							int(input("Enter number of vertices: ").strip())
       _SCREAMING_SNAKE_CASE	 =							int(input("Enter number of edges: ").strip())

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

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

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









'''simple docstring'''


def 	__a(SCREAMING_SNAKE_CASE_  :					list[int]		,       SCREAMING_SNAKE_CASE_  :					list[int]		,       SCREAMING_SNAKE_CASE_  :					int    ):



    '''simple docstring'''





    return not any(
        neighbour == 1 and colored_vertices[i] == color
        for i, neighbour in enumerate(SCREAMING_SNAKE_CASE_    )    )


def 	__a(SCREAMING_SNAKE_CASE_  :					list[list[int]]		,       SCREAMING_SNAKE_CASE_  :					int		,       SCREAMING_SNAKE_CASE_  :					list[int]		,       SCREAMING_SNAKE_CASE_  :					int    ):



    '''simple docstring'''





    if index == len(SCREAMING_SNAKE_CASE_    ):
        return True

    # Recursive Step
    for i in range(SCREAMING_SNAKE_CASE_    ):
        if valid_coloring(graph[index]		,       SCREAMING_SNAKE_CASE_		,       SCREAMING_SNAKE_CASE_    ):
            # Color current vertex
            _lowerCAmelCase				=      i
            # Validate coloring
            if util_color(SCREAMING_SNAKE_CASE_		,       SCREAMING_SNAKE_CASE_		,       SCREAMING_SNAKE_CASE_		,       index + 1    ):
                return True
            # Backtrack
            _lowerCAmelCase				=      -1
    return False





def 	__a(SCREAMING_SNAKE_CASE_  :					list[list[int]]		,       SCREAMING_SNAKE_CASE_  :					int    ):



    '''simple docstring'''





    _lowerCAmelCase				=      [-1] * len(SCREAMING_SNAKE_CASE_    )

    if util_color(SCREAMING_SNAKE_CASE_		,       SCREAMING_SNAKE_CASE_		,       SCREAMING_SNAKE_CASE_		,       0    ):
        return colored_vertices

    return []


