# Input acceptance

import sys



file_input = sys.stdin



V, E, r = map(int, file_input.readline().split())



edges = []



for line in file_input:

    edges.append(tuple(map(int, line.split())))





# Bellman???Ford algorithm

distance = [float("inf")] * V

distance[r] = 0



for i in range(V):

    notUpdated = True

    for e in edges:

        t = e[1]

        temp_d = distance[e[0]] + e[2]

        if temp_d < distance[t]:

            distance[t] = temp_d

            notUpdated = False

    if notUpdated:

        break





# Output

if i == V - 1 and V != 1:

    print("NEGATIVE CYCLE")

else:

    print(*map(lambda x: str(x).upper(), distance), sep = '\n')

# Input acceptance

import sys



file_input = sys.stdin



V, E, r = map(int, file_input.readline().split())



edges = []



for line in file_input:

    edges.append(tuple(map(int, line.split())))





# Bellman???Ford algorithm

distance = [float("inf")] * V

distance[r] = 0

notUpdated = True



for i in range(V - 1):

    notUpdated = True

    for s, t, w in edges:

        temp_d = distance[s] + w

        if temp_d < distance[t]:

            distance[t] = temp_d

            notUpdated = False

    if notUpdated:

        break





# Output

if notUpdated:

    print(*map(lambda x: str(x).upper(), distance), sep = '\n')

else:

    flag = True

    for s, t, w in edges:

        temp_d = distance[s] + w

        if temp_d < distance[t]:

            print("NEGATIVE CYCLE")

            flag = False

            break

    if flag:

        print(*map(lambda x: str(x).upper(), distance), sep = '\n')

# Input acceptance
import sys

file_input = sys.stdin
V, E, r = map(int, file_input.readline().split())
edges = []
for line in file_input:
    edges.append(tuple(map(int, line.split())))
# Bellman???Ford algorithm
distance = [float("inf")] * V
distance[r] = 0
for i in range(V):
    notUpdated = True
    for e in edges:
        t = e[1]
        temp_d = distance[e[0]] + e[2]
        if temp_d < distance[t]:
            distance[t] = temp_d
            notUpdated = False
    if notUpdated:
        break
# Output
if i == V - 1 and V != 1:
    print("NEGATIVE CYCLE")
else:
    print(*map(lambda x: str(x).upper(), distance), sep="\n")

# Input acceptance
import sys

file_input = sys.stdin
V, E, r = map(int, file_input.readline().split())
edges = []
for line in file_input:
    edges.append(tuple(map(int, line.split())))
# Bellman???Ford algorithm
distance = [float("inf")] * V
distance[r] = 0
notUpdated = True
for i in range(V - 1):
    notUpdated = True
    for s, t, w in edges:
        temp_d = distance[s] + w
        if temp_d < distance[t]:
            distance[t] = temp_d
            notUpdated = False
    if notUpdated:
        break
# Output
if notUpdated:
    print(*map(lambda x: str(x).upper(), distance), sep="\n")
else:
    flag = True
    for s, t, w in edges:
        temp_d = distance[s] + w
        if temp_d < distance[t]:
            print("NEGATIVE CYCLE")
            flag = False
            break
    if flag:
        print(*map(lambda x: str(x).upper(), distance), sep="\n")

-for i in range(V): +notUpdated = True +for i in range(V - 1): -    for e in edges: -        t = e[1] -        temp_d = distance[e[0]] + e[2] +    for s, t, w in edges: +        temp_d = distance[s] + w -if i == V - 1 and V != 1: -    print("NEGATIVE CYCLE") +if notUpdated: +    print(*map(lambda x: str(x).upper(), distance), sep="\n") -    print(*map(lambda x: str(x).upper(), distance), sep="\n") +    flag = True +    for s, t, w in edges: +        temp_d = distance[s] + w +        if temp_d < distance[t]: +            print("NEGATIVE CYCLE") +            flag = False +            break +    if flag: +        print(*map(lambda x: str(x).upper(), distance), sep="\n")