Bellman-Ford- distance bw src to all nodes with negative edges

'''
Dijktra doesn't work with the negative edges graphs, if there is a path weight or full cycle distance is less than 0, It will go for TLE.
#Bellman ford algorithm only works with the Directed graph, so if we are having the Undirected, make it directed graph but adding two edges,a->b and b->a.
#Bellman ford doesn't work with a negative cycle.
#Do the N-1 iteration where each iteration will relax the edges given N=Number of vertices and edges can be in any order.
#Why N-1 iteration? Because In worst case, it might take you N-1 iteration to find distance from source to all the nodes.
#How to detect a negative cycle in the graph? -> If the distance array gets updated at Nth iteration also, It is having a negative cycle loop because negative cycle will be having some negative value for eg. -1 then every iteration will reduce the distance by -1.

Why do we only visit n-1 times only?
because The longest possible shortest path in a graph can contain at most n-1 edges.a shortest path cannot keep revisiting nodes (that would create a cycle).

'''
# from math import inf
INF=pow(10,8)
class Solution:
    def bellmanFord(self, v, edges, src):
        dist=[INF]*v
        dist[src]=0
        for i in range(v): #It will iterate V times but we need only v-1 times so we kept vth iteration to check the negative cycle.
            for a,b,w in edges:
                if dist[a]==INF:
                    continue
                if dist[a]+w<dist[b]:
                    if i==v-1:
                        return [-1]
                    dist[b]=dist[a]+w #if the distance also got relaxed in last iteration ie. vth iteration means there is negative cycle.

        return dist