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



INF = 2 << 21

G = [[] for i in range(V)]

dist = [INF for j in range(V)]





def bellman_ford(s):

    p, flg = [-1 for i in range(V)], [False for i in range(V)]

    dist[s], flg[s], cnt = 0, True, 0



    while True:

        if cnt >= 2 * V:

            return False



        on = []

        for i in range(V):

            if flg[i]:

                on.append(i)

                flg[i] = False



        if len(on) == 0:

            return True



        for i in on:

            for j in G[i]:

                if dist[i] + j[1] < dist[j[0]]:

                    dist[j[0]] = dist[i] + j[1]

                    p[j[0]], flg[j[0]] = i, True



        cnt += 1





def main():

    for i in range(E):

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

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



    check = bellman_ford(r)



    if check:

        for i in range(V):

            if dist[i] == INF:

                print("INF")

            else:

                print((dist[i]))

    else:

        print("NEGATIVE CYCLE")





if __name__ == '__main__':

    main()



from collections import deque



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



INF = 2 << 21

G = [[] for i in range(V)]

dist = [INF for j in range(V)]





def bellman_ford(s):

    p, q1 = [-1 for i in range(V)], deque()

    dist[s], cnt = 0, 0

    q1.append(s)



    while True:

        if cnt >= 2 * V:

            return False



        if len(q1) == 0:

            return True



        q2 = deque()

        for i in q1:

            for j in G[i]:

                if dist[i] + j[1] < dist[j[0]]:

                    dist[j[0]], p[j[0]] = dist[i] + j[1], i

                    q2.append(j[0])



        q1 = q2

        cnt += 1





def main():

    for i in range(E):

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

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



    check = bellman_ford(r)



    if check:

        for i in range(V):

            if dist[i] == INF:

                print("INF")

            else:

                print((dist[i]))

    else:

        print("NEGATIVE CYCLE")





if __name__ == '__main__':

    main()



V, E, r = list(map(int, input().split()))
INF = 2 << 21
G = [[] for i in range(V)]
dist = [INF for j in range(V)]


def bellman_ford(s):
    p, flg = [-1 for i in range(V)], [False for i in range(V)]
    dist[s], flg[s], cnt = 0, True, 0
    while True:
        if cnt >= 2 * V:
            return False
        on = []
        for i in range(V):
            if flg[i]:
                on.append(i)
                flg[i] = False
        if len(on) == 0:
            return True
        for i in on:
            for j in G[i]:
                if dist[i] + j[1] < dist[j[0]]:
                    dist[j[0]] = dist[i] + j[1]
                    p[j[0]], flg[j[0]] = i, True
        cnt += 1


def main():
    for i in range(E):
        s, t, d = list(map(int, input().split()))
        G[s].append((t, d))
    check = bellman_ford(r)
    if check:
        for i in range(V):
            if dist[i] == INF:
                print("INF")
            else:
                print((dist[i]))
    else:
        print("NEGATIVE CYCLE")


if __name__ == "__main__":
    main()

from collections import deque

V, E, r = list(map(int, input().split()))
INF = 2 << 21
G = [[] for i in range(V)]
dist = [INF for j in range(V)]


def bellman_ford(s):
    p, q1 = [-1 for i in range(V)], deque()
    dist[s], cnt = 0, 0
    q1.append(s)
    while True:
        if cnt >= 2 * V:
            return False
        if len(q1) == 0:
            return True
        q2 = deque()
        for i in q1:
            for j in G[i]:
                if dist[i] + j[1] < dist[j[0]]:
                    dist[j[0]], p[j[0]] = dist[i] + j[1], i
                    q2.append(j[0])
        q1 = q2
        cnt += 1


def main():
    for i in range(E):
        s, t, d = list(map(int, input().split()))
        G[s].append((t, d))
    check = bellman_ford(r)
    if check:
        for i in range(V):
            if dist[i] == INF:
                print("INF")
            else:
                print((dist[i]))
    else:
        print("NEGATIVE CYCLE")


if __name__ == "__main__":
    main()

+from collections import deque + -    p, flg = [-1 for i in range(V)], [False for i in range(V)] -    dist[s], flg[s], cnt = 0, True, 0 +    p, q1 = [-1 for i in range(V)], deque() +    dist[s], cnt = 0, 0 +    q1.append(s) -        on = [] -        for i in range(V): -            if flg[i]: -                on.append(i) -                flg[i] = False -        if len(on) == 0: +        if len(q1) == 0: -        for i in on: +        q2 = deque() +        for i in q1: -                    dist[j[0]] = dist[i] + j[1] -                    p[j[0]], flg[j[0]] = i, True +                    dist[j[0]], p[j[0]] = dist[i] + j[1], i +                    q2.append(j[0]) +        q1 = q2