class Solution {
  public:
    /*  Function to implement Bellman Ford
    *   edges: vector of vectors which represents the graph
    *   S: source vertex to start traversing graph with
    *   V: number of vertices
    */
    vector<int> bellman_ford(int V, vector<vector<int>>& edges, int S) {
        // Code here
        //iterate through edges ond keep on updating the distance array. Iterate through all the edges for 
        //V-1 times
        vector<int> dis(V,1e8);
        dis[S]=0;
        for(int i=0;i<V-1;i++){
            
            for(int j =0;j<edges.size();j++){
                int u = edges[j][0];
                int v = edges[j][1];
                int w = edges[j][2];
                if(dis[u] != 1e8 && dis[u]+w<dis[v]){
                    dis[v]=dis[u]+w;
                }
            }
        }
        for(int i=0;i<1;i++){
            
            for(int j =0;j<edges.size();j++){
                int u = edges[j][0];
                int v = edges[j][1];
                int w = edges[j][2];
                if(dis[u] != 1e8 && dis[u]+w<dis[v]){
                    return {-1};
                }
            }
        }
        
        return dis;
    }
};