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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String[] tmpArray = br.readLine().split(" ");

		//0 origin
		int n = Integer.parseInt(tmpArray[0]);
		int m = Integer.parseInt(tmpArray[1]);
		int x = Integer.parseInt(tmpArray[2]);

		Edge edges[] = new Edge[m];

		for(int i = 0; i < m; i++){
			tmpArray = br.readLine().split(" ");
			int from = Integer.parseInt(tmpArray[0]);
			int to = Integer.parseInt(tmpArray[1]);
			int cost = Integer.parseInt(tmpArray[2]);

			edges[i] = new Edge(from, to, cost);
		}

		solve(edges, n, x);
	}

//	static final int INF = 10_000_001;

	static void solve(Edge[] edges,  int n, int x){
		//xからそれぞれのfarmへの帰り道の最短距離
		int[] dist = shortestPath(edges, n, x);

		if(dist == null){
			System.out.println("NEGATIVE CYCLE");
			return;
		}

		for(int i = 0; i < n; i++){
			if(dist[i] == INF){
				System.out.println("INF");
			}
			else {
				System.out.println(dist[i]);
			}
		}

	}

	static final int INF = Integer.MAX_VALUE;


	static int[] shortestPath(Edge[] edges, int n, int s){
		int dist[] = new int[n];

		Arrays.fill(dist, INF);
		dist[s] = 0;

		int e = edges.length;

		int k = 0;
		while(true){
			boolean update = false;

			for(int i = 0; i < e; i++){
				Edge edge = edges[i];
				if(dist[edge.from] != INF && dist[edge.to] > dist[edge.from] + edge.cost){
					dist[edge.to] = dist[edge.from] + edge.cost;
					update = true;

//					System.out.println("dist:"+edge.to+" is "+dist[edge.to]);

					if(k == n - 1){
						return null;
					}
				}
			}

			if(!update){
				break;
			}

			k++;
		}

		return dist;
	}
}
//
//class Distance implements Comparable<Distance>{
//	int dist;
//	int id;
//
//	Distance(int dist, int id){
//		this.dist = dist;
//		this.id = id;
//	}
//
//	@Override
//	public int compareTo(Distance d) {
//		return this.dist - d.dist;
//	}
//}

class Edge {
	int from;
	int to;
	int cost;

	Edge(int from, int to, int cost){
		this.from = from;
		this.to = to;
		this.cost = cost;
	}
}