// User function Template for Java
class iPair 
{
    int vertex;
    int weight;
    iPair(int vertex, int weight)
    {
        this.vertex = vertex;
        this.weight = weight;
    }
}
 
class Pair 
{
    int node;
    int dist;
    Pair(int node, int dist)
    {
        this.node = node;
        this.dist = dist;
    }
}
 
class Solution {
    // Diff: In dijkstra we do not have cycle in weighted, undirected, connected graph but here we can have cycle
 
    /**
     * Idea
     * 1. Create a distance array and assign values as (int)1e8
     * 2. Relax the edges N-1 times
     * 3. Now relax the edges again and see if you if relaxation is possible
     *      - if possible then we have negative cycle, return array of -1 element
     *      - else keep continuing
     * 4. At last return distance array
     */
    public int[] bellmanFord(int V, int[][] edges, int src) {
        // Step-1 create a distance array
        int[] distance = new int[V];
        Arrays.fill(distance, (int)1e8);
        distance[src] = 0;
 
 
        // Step-2 Relax edges V-1 times
        for(int i=0; i<V-1; i++) 
        {
            for(int[] edge : edges) 
            {
                int u = edge[0];
                int v = edge[1];
                int w = edge[2];
 
                if(distance[u] != (int)1e8 && distance[v] > distance[u] + w) 
                {
                    distance[v] = distance[u] + w;
                }
            }
        }
 
        // Step-3 to detect negative cycle
        for(int[] edge : edges) 
        {
            int u = edge[0];
            int v = edge[1];
            int w = edge[2];
 
            if(distance[u] != (int)1e8 && distance[v] > distance[u] + w) 
            {
                return new int[]{-1};
            }
        }    
        return distance;
    }
}