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 PYTHON3):

Solution:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
4 5 1
0 1 2
0 2 3
1 2 -5
1 3 1
2 3 2

output:
INF
0
-5
-3

OR
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
"""

import sys
from math import isinf


class Edge(object):
    __slots__ = ('source', 'target', 'cost')

    def __init__(self):
        self.cost = float('inf')
        self.source, self.target = None, None


def generate_edge_table(_v_info):
    for index, each in enumerate(_v_info):
        edge = init_edge_table[index]
        source, target, cost = map(int, each)
        edge.source = source
        edge.target = target
        edge.cost = cost
    return init_edge_table


def bellman_ford():
    distance[root] = 0

    for j in range(vertices - 1):
        for edge in edge_table:
            source, target, cost = edge.source, edge.target, edge.cost
            if distance[source] + cost < distance[target]:
                distance[target] = distance[source] + cost

    for edge in edge_table:
        source, target, cost = edge.source, edge.target, edge.cost
        if distance[source] + cost < distance[target]:
            print('NEGATIVE CYCLE')
            return list()

    return distance


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices, edges, root = map(int, _input[0].split())
    v_info = map(lambda x: x.split(), _input[1:])
    # assert len(init_vertices_table) == vertices_num

    distance = [float('inf')] * vertices
    init_edge_table = tuple(Edge() for _ in range(edges))

    edge_table = generate_edge_table(v_info)

    res = bellman_ford()
    for ele in res:
        if isinf(ele):
            print('INF')
        else:
            print(ele)