import java.util.*;

// Bellman-Ford Algorithm (Shortest Paths with possible negative weights)
class BellmanFordAlgorithm {

    // Edge representation (u -> v with weight w)
    static class Edge {
        int src, dest, weight;
        Edge(int s, int d, int w) {
            this.src = s;
            this.dest = d;
            this.weight = w;
        }
    }

    public static void bellmanFord(int V, List edges, int source) {
        // Step 1: Initialize distance array
        // ---------------------------------
        // dist[i] = shortest distance from source to i
        // Initially, set everything to infinity except the source
        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[source] = 0;

        // 💡 Intuition:
        // The shortest path in a graph without cycles can have at most (V-1) edges.
        // So, relaxing edges (V-1) times guarantees the shortest distance to each vertex.

        // Step 2: Relax all edges V-1 times
        // ----------------------------------
        // Outer loop runs (V-1) times → ensures we propagate shortest paths fully.
        // Each iteration scans all edges → O(V * E)
        for (int i = 1; i <= V - 1; i++) {
            // For every edge, try to improve the shortest path estimate
            for (Edge e : edges) {
                int u = e.src;
                int v = e.dest;
                int w = e.weight;

                // If source node is reachable and relaxation gives a better path
                if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                }
            }
        }

        // Step 3: Check for negative weight cycles
        // -----------------------------------------
        // Perform one more relaxation — if any distance improves,
        // it means there's a cycle with net negative weight.
        boolean hasNegativeCycle = false;
        for (Edge e : edges) {
            int u = e.src;
            int v = e.dest;
            int w = e.weight;
            if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
                hasNegativeCycle = true;
                break;
            }
        }

        // Step 4: Output result
        // ----------------------
        if (hasNegativeCycle) {
            System.out.println("Graph contains a NEGATIVE WEIGHT CYCLE!");
        } else {
            System.out.println("Shortest distances from source " + source + ":");
            for (int i = 0; i < V; i++) {
                System.out.println("Node " + i + " → " +
                        (dist[i] == Integer.MAX_VALUE ? "∞" : dist[i]));
            }
        }
    }

    public static void main(String[] args) {
        // Example Graph:
        // Edges:
        // 0 -> 1 (4)
        // 0 -> 2 (5)
        // 1 -> 2 (-3)
        // 2 -> 3 (4)
        // 3 -> 1 (2)
        // This graph has no negative cycle.

        int V = 4; // number of vertices
        List edges = new ArrayList<>();

        edges.add(new Edge(0, 1, 4));
        edges.add(new Edge(0, 2, 5));
        edges.add(new Edge(1, 2, -3));
        edges.add(new Edge(2, 3, 4));
        edges.add(new Edge(3, 1, 2));

        bellmanFord(V, edges, 0);
    }
}