import sys

readline = sys.stdin.readline



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

inf = 10**10

edges = [[] for _ in [None]*V]



for _ in [None]*E:

    s, t, d = list(map(int, readline().split()))

    edges[s].append((t, d))



vertices = [inf] * V

vertices[r] = 0



for i in range(V):

    flag = 0

    for v in range(V):

        cost = vertices[v]

        if cost == inf:

            continue

        for dist, _cost in edges[v]:

            newcost = cost + _cost

            if vertices[dist] > newcost:

                vertices[dist] = newcost

                flag = 1

    if flag == 0:

        for v in vertices:

            print((v if v != inf else "INF"))

        break

else:

    print("NEGATIVE CYCLE")
import sys

readline = sys.stdin.readline



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

inf = 10**10

edges = [[] for _ in [None]*V]



for _ in [None]*E:

    s, t, d = list(map(int, readline().split()))

    edges[s].append((t, d))





def bellman_ford(n, edges, start):

    vertices = [inf] * n

    vertices[start] = 0

    reached = {start}



    for i in range(n):

        flag = 0

        for v in reached.copy():

            cost = vertices[v]

            for dist, _cost in edges[v]:

                newcost = cost + _cost

                if vertices[dist] > newcost:

                    vertices[dist] = newcost

                    reached.add(dist)

                    flag = 1

        if flag == 0:

            return vertices

    else:

        return None



result = bellman_ford(V, edges, r)

if result:

    print(("\n".join([str(n) if n!=inf else "INF" for n in result])))

else:

    print("NEGATIVE CYCLE")
import sys

readline = sys.stdin.readline
V, E, r = list(map(int, readline().split()))
inf = 10**10
edges = [[] for _ in [None] * V]
for _ in [None] * E:
    s, t, d = list(map(int, readline().split()))
    edges[s].append((t, d))
vertices = [inf] * V
vertices[r] = 0
for i in range(V):
    flag = 0
    for v in range(V):
        cost = vertices[v]
        if cost == inf:
            continue
        for dist, _cost in edges[v]:
            newcost = cost + _cost
            if vertices[dist] > newcost:
                vertices[dist] = newcost
                flag = 1
    if flag == 0:
        for v in vertices:
            print((v if v != inf else "INF"))
        break
else:
    print("NEGATIVE CYCLE")

import sys

readline = sys.stdin.readline
V, E, r = list(map(int, readline().split()))
inf = 10**10
edges = [[] for _ in [None] * V]
for _ in [None] * E:
    s, t, d = list(map(int, readline().split()))
    edges[s].append((t, d))


def bellman_ford(n, edges, start):
    vertices = [inf] * n
    vertices[start] = 0
    reached = {start}
    for i in range(n):
        flag = 0
        for v in reached.copy():
            cost = vertices[v]
            for dist, _cost in edges[v]:
                newcost = cost + _cost
                if vertices[dist] > newcost:
                    vertices[dist] = newcost
                    reached.add(dist)
                    flag = 1
        if flag == 0:
            return vertices
    else:
        return None


result = bellman_ford(V, edges, r)
if result:
    print(("\n".join([str(n) if n != inf else "INF" for n in result])))
else:
    print("NEGATIVE CYCLE")

-vertices = [inf] * V -vertices[r] = 0 -for i in range(V): -    flag = 0 -    for v in range(V): -        cost = vertices[v] -        if cost == inf: -            continue -        for dist, _cost in edges[v]: -            newcost = cost + _cost -            if vertices[dist] > newcost: -                vertices[dist] = newcost -                flag = 1 -    if flag == 0: -        for v in vertices: -            print((v if v != inf else "INF")) -        break + + +def bellman_ford(n, edges, start): +    vertices = [inf] * n +    vertices[start] = 0 +    reached = {start} +    for i in range(n): +        flag = 0 +        for v in reached.copy(): +            cost = vertices[v] +            for dist, _cost in edges[v]: +                newcost = cost + _cost +                if vertices[dist] > newcost: +                    vertices[dist] = newcost +                    reached.add(dist) +                    flag = 1 +        if flag == 0: +            return vertices +    else: +        return None + + +result = bellman_ford(V, edges, r) +if result: +    print(("\n".join([str(n) if n != inf else "INF" for n in result])))