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





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')

    weights = [INF] * nvertices

    weights[s] = 0

    for i in range(nvertices - 1):

        for u, v, w in E:

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

                weights[v] = weights[u] + w

    for u, v, w in E:

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

            print("NEGATIVE CYCLE")

            return



    for w in weights:

        if math.isinf(w):

            print("INF")

        else:

            print(w)





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


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")
    weights = [INF] * nvertices
    weights[s] = 0
    for i in range(nvertices - 1):
        for u, v, w in E:
            if weights[v] > weights[u] + w:
                weights[v] = weights[u] + w
    for u, v, w in E:
        if weights[v] > weights[u] + w:
            print("NEGATIVE CYCLE")
            return
    for w in weights:
        if math.isinf(w):
            print("INF")
        else:
            print(w)


main()

-    d = [INF] * nvertices -    d[s] = 0 +    weights = [INF] * nvertices +    weights[s] = 0 -            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): +            if weights[v] > weights[u] + w: +                weights[v] = weights[u] + w +    for u, v, w in E: +        if weights[v] > weights[u] + w: +            print("NEGATIVE CYCLE") +            return +    for w in weights: +        if math.isinf(w): -            print(val) +            print(w)