def main():

    nvertices, nedges, s = list(map(int, input().split()))

    E = []

    for i in range(nedges):

        u, v, w = list(map(int, input().split()))

        E.append((u, v, w))



    INF = 1000000000

    d = [INF] * nvertices

    d[s] = 0

    for i in range(nvertices - 1):

        for u, v, w in E:

            if d[u] == INF:

                continue

            if d[u] + w < d[v]:

                d[v] = d[u] + w



    for i in range(nvertices - 1):

        for u, v, w in E:

            if d[v] == INF:

                continue

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

                print("NEGATIVE CYCLE")

                return



    for val in d:

        if val >= INF:

            print("INF")

        else:

            print(val)





main()
import math





def main():

    nvertices, nedges, s = list(map(int, input().split()))

    E = []

    for i in range(nedges):

        u, v, w = list(map(int, input().split()))

        E.append((u, v, w))



    INF = float('inf')

    d = [INF] * nvertices

    d[s] = 0

    for i in range(nvertices - 1):

        for u, v, w in E:

            if d[u] + w < d[v]:

                d[v] = d[u] + w



    for i in range(nvertices - 1):

        for u, v, w in E:

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

                print("NEGATIVE CYCLE")

                return



    for val in d:

        if math.isinf(val):

            print("INF")

        else:

            print(val)





main()
def main():
    nvertices, nedges, s = list(map(int, input().split()))
    E = []
    for i in range(nedges):
        u, v, w = list(map(int, input().split()))
        E.append((u, v, w))
    INF = 1000000000
    d = [INF] * nvertices
    d[s] = 0
    for i in range(nvertices - 1):
        for u, v, w in E:
            if d[u] == INF:
                continue
            if d[u] + w < d[v]:
                d[v] = d[u] + w
    for i in range(nvertices - 1):
        for u, v, w in E:
            if d[v] == INF:
                continue
            if d[v] > d[u] + w:
                print("NEGATIVE CYCLE")
                return
    for val in d:
        if val >= INF:
            print("INF")
        else:
            print(val)


main()

import math


def main():
    nvertices, nedges, s = list(map(int, input().split()))
    E = []
    for i in range(nedges):
        u, v, w = list(map(int, input().split()))
        E.append((u, v, w))
    INF = float("inf")
    d = [INF] * nvertices
    d[s] = 0
    for i in range(nvertices - 1):
        for u, v, w in E:
            if d[u] + w < d[v]:
                d[v] = d[u] + w
    for i in range(nvertices - 1):
        for u, v, w in E:
            if d[v] > d[u] + w:
                print("NEGATIVE CYCLE")
                return
    for val in d:
        if math.isinf(val):
            print("INF")
        else:
            print(val)


main()

+import math + + -    INF = 1000000000 +    INF = float("inf") -            if d[u] == INF: -                continue -            if d[v] == INF: -                continue -        if val >= INF: +        if math.isinf(val):