def bellman_ford(edges, n, source):
    """This implementation takes in a graph, represented as lists of vertices
    (represented as integers [0..n-1]) and edges, and fills two arrays
    (distance and predecessor) holding the shortest path from the source to
    each vertex

    NOTE: vertices start from 0
    Examples:
    >>> edges = [
    >>>    (0, 1, 2), (1, 2, 2), (2, 3, 2),
    >>>    (0, 4, 4), (4, 3, 4), (1, 4, 1)
    >>>    ]
    >>> dist = bellman_ford(edges, 5, 0)
    >>> print(dist)
    [0, 2, 4, 6, 3]

    >>> edges = [
    >>>    (0, 1, 2), (1, 2, 2), (2, 3, 2),
    >>>    (4, 0, 1), (4, 3, 4), (1, 4, -5)
    >>>    ]
    >>> dist = bellman_ford(edges, 5, 0)
    >>> print(dist)
    Graph contains a negative-weight cycle
    None
    """

    # Step 1: initialize graph
    weights = [e[2] for e in edges]
    dist = [max(weights) * n] * n
    predecessor = [None] * n

    dist[0] = 0
    # Step 2: relax edges |V|−1 times
    for i in range(n-1):
        for (u, v, w) in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                predecessor[v] = u
    # Step 3: check for negative-weight cycles
    for (u, v, w) in edges:
        if dist[u] + w < dist[v]:
            print("Graph contains a negative-weight cycle")
            return None

    return dist