Problem: Constraints

* 1 ≤ |V| ≤ 1000
* 0 ≤ |E| ≤ 2000
* -10000 ≤ di ≤ 10000
* There are no parallel edges
* There are no self-loops

Input

An edge-weighted graph G (V, E) and the source r.


|V| |E| r
s0 t0 d0
s1 t1 d1
:
s|E|-1 t|E|-1 d|E|-1


|V| is the number of vertices and |E| is the number of edges in G. The graph vertices are named with the numbers 0, 1,..., |V|-1 respectively. r is the source of the graph.

si and ti represent source and target vertices of i-th edge (directed) and di represents the cost of the i-th edge.

Output

If the graph contains a negative cycle (a cycle whose sum of edge costs is a negative value) which is reachable from the source r, print


NEGATIVE CYCLE


in a line.

Otherwise, print


c0
c1
:
c|V|-1


The output consists of |V| lines. Print the cost of the shortest path from the source r to each vertex 0, 1, ... |V|-1 in order. If there is no path from the source to a vertex, print "INF".

Examples

Input

4 5 0
0 1 2
0 2 3
1 2 -5
1 3 1
2 3 2


Output

0
2
-3
-1


Input

4 6 0
0 1 2
0 2 3
1 2 -5
1 3 1
2 3 2
3 1 0


Output

NEGATIVE CYCLE


Input

4 5 1
0 1 2
0 2 3
1 2 -5
1 3 1
2 3 2


Output

INF
0
-5
-3

Solution (in JAVA):

Solution:

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    public static class BellmanFordShortestPath {

        Integer[] distTo; // index is vertex
        Integer[] edgeTo;
        boolean hasNegativeCycle;
        WeightedDigraph graph;
        int sourceVertex;
        Queue<Integer> changedVertQueue;

        public BellmanFordShortestPath(WeightedDigraph graph, int sourceVertex) {
            this.graph = graph;
            this.sourceVertex = sourceVertex;
            distTo = new Integer[graph.numVertex];
            edgeTo = new Integer[graph.numVertex];
            distTo[sourceVertex] = 0;
            edgeTo[sourceVertex] = 0;

            changedVertQueue = new LinkedList<Integer>();
            changedVertQueue.add(sourceVertex);

            // At most V + 1 passes instead of V, the extra pass is used to detect negative cycle
            for (int pass = 0; pass <= graph.numVertex; pass++) {
                relaxAll();
                if (changedVertQueue.isEmpty()) {
                    break;
                } else if (pass == graph.numVertex) {
                    hasNegativeCycle = true;
                }
            }
        }

        private void relaxAll() {
            boolean[] onQ = new boolean[graph.numVertex];
            Integer[] verts = changedVertQueue.toArray(new Integer[0]);
            changedVertQueue.clear();
            for (int vertex : verts) {
                for (WeightedDigraph.Edge edge : graph.srcEdges[vertex]) {
                    int src = edge.srcVertex;
                    int dest = edge.targetVertex;
                    if (distTo[src] != null && (distTo[dest] == null
                            || distTo[dest] > distTo[src] + edge.weight)) {
                        distTo[dest] = distTo[src] + edge.weight;
                        edgeTo[dest] = src;
                        if (!onQ[dest]) {
                            changedVertQueue.add(dest);
                            onQ[dest] = true;
                        }
                    }
                }
            }
        }

        public boolean hasNegativeCycle() {
            return hasNegativeCycle;
        }

        /**
         *
         * @param vertex
         * @return null meaning INF
         */
        public Integer shortestPath(int vertex) {
            return distTo[vertex];
        }

        public List<Integer> paths(int vertex) {
            LinkedList<Integer> paths = new LinkedList<Integer>();
            while (edgeTo[vertex] != null) {
                paths.addFirst(edgeTo[vertex]);
                if (edgeTo[vertex] != vertex) {
                    vertex = edgeTo[vertex];
                } else {
                    break;
                }
            }
            return paths;
        }

    }

    public static class WeightedDigraph {

        int numVertex;
        int numEdge;

        List<Edge>[] srcEdges;

        @SuppressWarnings("unchecked")
        public WeightedDigraph(int numV, int numE) {
            this.numVertex = numV;
            this.numEdge = numE;
            srcEdges = new List[numV];

            for (int i = 0; i < numV; i++) {
                srcEdges[i] = new ArrayList<Edge>();
            }
        }

        public void addEdge(int srcVertex, int targetVertex, int weight) {
            Edge e = new WeightedDigraph.Edge(srcVertex, targetVertex, weight);
            srcEdges[srcVertex].add(e);
        }

        public static class Edge {

            int srcVertex;
            int targetVertex;
            int weight;

            public Edge(int srcVertex, int targetVertex, int weight) {
                this.srcVertex = srcVertex;
                this.targetVertex = targetVertex;
                this.weight = weight;
            }
        }

    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int numVertex = scanner.nextInt();
        int numEdge = scanner.nextInt();
        WeightedDigraph graph = new WeightedDigraph(numVertex, numEdge);
        int srcVertex = scanner.nextInt();
        while (numEdge-- > 0) {
            int srcV = scanner.nextInt();
            int targetV = scanner.nextInt();
            int weight = scanner.nextInt();
            graph.addEdge(srcV, targetV, weight);
        }
        BellmanFordShortestPath bellmanFord = new BellmanFordShortestPath(graph, srcVertex);
        if (bellmanFord.hasNegativeCycle()) {
            System.out.println("NEGATIVE CYCLE");
        } else {
            for (int i = 0; i < graph.numVertex; i++) {
                Integer v = bellmanFord.shortestPath(i);
                System.out.println(v == null ? "INF" : v);
            }
        }
    }

}