Bellman-Ford Algorithm

def bellman_ford(graph, start):
    # graph is a list of edges in the format (u, v, w)
    num_vertices = len(set(u for u, v, w in graph) | set(v for u, v, w in graph))
    distances = {i: float('Infinity') for i in range(num_vertices)}
    distances[start] = 0

    for _ in range(num_vertices - 1):
        for u, v, w in graph:
            if distances[u] != float('Infinity') and distances[u] + w < distances[v]:
                distances[v] = distances[u] + w

    # Check for negative weight cycles
    for u, v, w in graph:
        if distances[u] != float('Infinity') and distances[u] + w < distances[v]:
            return "Graph contains a negative weight cycle"

    return distances