from sys import stdin

from collections import deque



V, E, R = [int(x) for x in stdin.readline().split()]

d = {}

tick = False

INF = float('inf')

for i in range(V):

    d[i] = INF

d[R] = 0

weight = {}

st = []

for i in range(1, V+1):

    for j in range(E):

        if i == 1:

            s, t, w = [int(x) for x in stdin.readline().split()]

            weight[(s, t)] = w

            st.append((s, t))

        (s, t) = st[j]

        if d[t] > d[s] + weight[(s, t)]:

            d[t] = d[s] + weight[(s, t)]

            if i == V:

                print('NEGATIVE CYCLE')

                quit()



for k in range(V):

    if d[k] == float('inf'):

        print("INF")

    else:

        print((d[k]))
from collections import defaultdict

from collections import deque

from sys import stdin

 

def sp(G,R,V):

    d = {}

    INF = float('inf')

    for i in range(V):

        d[i] = INF

    d[R] = 0

    for i in range(1, V+1):

        for ((u, v), c) in list(G.items()):

            if d[v] > d[u] + c:

                d[v] = d[u] + c

                if i == V:

                    return 0

    return d

 

 

V, E, R = [int(x) for x in stdin.readline().split()]

G = {}

for case in range(E):

    s, t, w = [int(x) for x in stdin.readline().split()]

    G[(s, t)] = w

d = sp(G, R, V)

if d == 0:

    print('NEGATIVE CYCLE')

else:

    for k in range(V):

        if d[k] == float('inf'):

            print("INF")

        else:

            print((d[k]))
from sys import stdin
from collections import deque

V, E, R = [int(x) for x in stdin.readline().split()]
d = {}
tick = False
INF = float("inf")
for i in range(V):
    d[i] = INF
d[R] = 0
weight = {}
st = []
for i in range(1, V + 1):
    for j in range(E):
        if i == 1:
            s, t, w = [int(x) for x in stdin.readline().split()]
            weight[(s, t)] = w
            st.append((s, t))
        (s, t) = st[j]
        if d[t] > d[s] + weight[(s, t)]:
            d[t] = d[s] + weight[(s, t)]
            if i == V:
                print("NEGATIVE CYCLE")
                quit()
for k in range(V):
    if d[k] == float("inf"):
        print("INF")
    else:
        print((d[k]))

from collections import defaultdict
from collections import deque
from sys import stdin


def sp(G, R, V):
    d = {}
    INF = float("inf")
    for i in range(V):
        d[i] = INF
    d[R] = 0
    for i in range(1, V + 1):
        for ((u, v), c) in list(G.items()):
            if d[v] > d[u] + c:
                d[v] = d[u] + c
                if i == V:
                    return 0
    return d


V, E, R = [int(x) for x in stdin.readline().split()]
G = {}
for case in range(E):
    s, t, w = [int(x) for x in stdin.readline().split()]
    G[(s, t)] = w
d = sp(G, R, V)
if d == 0:
    print("NEGATIVE CYCLE")
else:
    for k in range(V):
        if d[k] == float("inf"):
            print("INF")
        else:
            print((d[k]))

+from collections import defaultdict +from collections import deque -from collections import deque + + +def sp(G, R, V): +    d = {} +    INF = float("inf") +    for i in range(V): +        d[i] = INF +    d[R] = 0 +    for i in range(1, V + 1): +        for ((u, v), c) in list(G.items()): +            if d[v] > d[u] + c: +                d[v] = d[u] + c +                if i == V: +                    return 0 +    return d + -d = {} -tick = False -INF = float("inf") -for i in range(V): -    d[i] = INF -d[R] = 0 -weight = {} -st = [] -for i in range(1, V + 1): -    for j in range(E): -        if i == 1: -            s, t, w = [int(x) for x in stdin.readline().split()] -            weight[(s, t)] = w -            st.append((s, t)) -        (s, t) = st[j] -        if d[t] > d[s] + weight[(s, t)]: -            d[t] = d[s] + weight[(s, t)] -            if i == V: -                print("NEGATIVE CYCLE") -                quit() -for k in range(V): -    if d[k] == float("inf"): -        print("INF") -    else: -        print((d[k])) +G = {} +for case in range(E): +    s, t, w = [int(x) for x in stdin.readline().split()] +    G[(s, t)] = w +d = sp(G, R, V) +if d == 0: +    print("NEGATIVE CYCLE") +else: +    for k in range(V): +        if d[k] == float("inf"): +            print("INF") +        else: +            print((d[k]))