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

    edges = []

    for i in range(nedges):

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

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



    INF = float('inf')

    weights = [INF] * nvertices

    weights[s] = 0

    for i in range(nvertices - 1):

        for u, v, w in edges:

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

                weights[v] = weights[u] + w



    for u, v, w in edges:

        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")
    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()))
    edges = []
    for i in range(nedges):
        u, v, w = list(map(int, input().split()))
        edges.append((u, v, w))
    INF = float("inf")
    weights = [INF] * nvertices
    weights[s] = 0
    for i in range(nvertices - 1):
        for u, v, w in edges:
            if weights[v] > weights[u] + w:
                weights[v] = weights[u] + w
    for u, v, w in edges:
        if weights[v] > weights[u] + w:
            print("NEGATIVE CYCLE")
            return
    for w in weights:
        if math.isinf(w):
            print("INF")
        else:
            print(w)


main()

-    E = [] +    edges = [] -        E.append((u, v, w)) +        edges.append((u, v, w)) -        for u, v, w in E: +        for u, v, w in edges: -    for u, v, w in E: +    for u, v, w in edges: