human
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
# htt
assistant
#Here is Python program to print the cost of the shortest path from the source r to each vertex 0, 1, .
p://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_B&lang=ja
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

class BellmanFord:
    """
    shortest_distance(goal): startノードからgoalノードまでの最短距離
    shortest_path(goal): startノードからgoalノードまでの最短経路
    include_negative_cycle(): 負閉路の存在確認
    """
    def __init__(self, V, edges, start):
        """
        V : 頂点数
        edges: (辺の始点,辺の終点,辺のコスト)を要素とする辺のリスト
        start: 始点のノード番号
        """
        self.V = V
        self.edges = edges
        self.start = start

    def include_negative_cycle(self):
        """
        負閉路の存在確認
        Returns: True or False
        """
        d = [0] * self.V
        for i in range(self.V):
            # start, end, cost
            for s, e, c in self.edges:
                if d[e] > d[s] + c:
                    d[e] = d[s] + c
                    # V回目にも更新があるなら負の閉路が存在する
                    if i == self.V-1:
                        return True
        return False
                    
    def shortest_distance(self):
        """ 
        始点から頂点goalまでの最短距離をを返す 
        """
        d = [float('inf')] * self.V
        d[self.start] = 0

        # 最短経路での1つ前のノードを保持するリスト
        self.prev = [None] * self.V

        loop_counter = 0
        while True:
            update = False
            # start, end, cost
            for s, e, c  in self.edges:
                if d[s] != float('inf') and d[e] > d[s] + c:
                    d[e] = d[s] + c
                    self.prev[e] = s
                    update = True
            
            loop_counter += 1
            if loop_counter == self.V and update:
                d[self.start] = float('inf')
                break

            if not update:
                break
        
        return d

    def shortest_path(self, goal):
        """
        始点から頂点goalまでの最短経路をを返す 
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
       ...