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

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

for i in range(E):

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

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



INF = 10**18

dist = [INF] * V

dist[r] = 0

update = 1

for _ in range(V):

    update = 0

    for v, e in enumerate(g):

        for t, cost in e:

            if dist[v]!=INF and dist[v] + cost < dist[t]:

                dist[t] = dist[v] + cost

                update = 1

    if not update:

        break

else:

    print("NEGATIVE CYCLE")

    exit(0)

for i in range(V):

    print(dist[i] if dist[i]<INF else "INF")
from collections import deque

N, M, r = list(map(int, input().split()))

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

for i in range(M):

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

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



INF = 10**18

def SPFA(N, G, s):

    dist = [INF] * N

    cont = [0] * N

    cnts = [0]* N



    dist[s] = 0

    cont[s] = 1

    cnts[s] += 1

    que = deque([s])

    su = s; num = 1

    while que:

        v = que.popleft()

        cont[v] = 0

        d = dist[v]

        su -= d

        num -= 1

        for w, c in G[v]:

            r = d + c

            if r < dist[w]:

                if not cont[w]:

                    cnts[w] += 1

                    if N <= cnts[w]:

                        return None

                    if que and r < que[0]:

                        que.appendleft(w)

                    else:

                        que.append(w)

                    cont[w] = 1

                    su += r

                    num += 1

                    dist[w] = r

                    while su < dist[que[0]]*num:

                        que.append(que.popleft())

                else:

                    su += r - dist[w]

                    dist[w] = r

    return dist

dist = SPFA(N, G, r)

if dist is None:

    print("NEGATIVE CYCLE")

else:

    for i in range(N):

        print((dist[i] if dist[i] < INF else "INF"))

V, E, r = list(map(int, input().split()))
g = [[] for i in range(V)]
for i in range(E):
    s, t, d = list(map(int, input().split()))
    g[s].append((t, d))
INF = 10**18
dist = [INF] * V
dist[r] = 0
update = 1
for _ in range(V):
    update = 0
    for v, e in enumerate(g):
        for t, cost in e:
            if dist[v] != INF and dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                update = 1
    if not update:
        break
else:
    print("NEGATIVE CYCLE")
    exit(0)
for i in range(V):
    print(dist[i] if dist[i] < INF else "INF")

from collections import deque

N, M, r = list(map(int, input().split()))
G = [[] for i in range(N)]
for i in range(M):
    s, t, d = list(map(int, input().split()))
    G[s].append((t, d))
INF = 10**18


def SPFA(N, G, s):
    dist = [INF] * N
    cont = [0] * N
    cnts = [0] * N
    dist[s] = 0
    cont[s] = 1
    cnts[s] += 1
    que = deque([s])
    su = s
    num = 1
    while que:
        v = que.popleft()
        cont[v] = 0
        d = dist[v]
        su -= d
        num -= 1
        for w, c in G[v]:
            r = d + c
            if r < dist[w]:
                if not cont[w]:
                    cnts[w] += 1
                    if N <= cnts[w]:
                        return None
                    if que and r < que[0]:
                        que.appendleft(w)
                    else:
                        que.append(w)
                    cont[w] = 1
                    su += r
                    num += 1
                    dist[w] = r
                    while su < dist[que[0]] * num:
                        que.append(que.popleft())
                else:
                    su += r - dist[w]
                    dist[w] = r
    return dist


dist = SPFA(N, G, r)
if dist is None:
    print("NEGATIVE CYCLE")
else:
    for i in range(N):
        print((dist[i] if dist[i] < INF else "INF"))

-V, E, r = list(map(int, input().split())) -g = [[] for i in range(V)] -for i in range(E): +from collections import deque + +N, M, r = list(map(int, input().split())) +G = [[] for i in range(N)] +for i in range(M): -    g[s].append((t, d)) +    G[s].append((t, d)) -dist = [INF] * V -dist[r] = 0 -update = 1 -for _ in range(V): -    update = 0 -    for v, e in enumerate(g): -        for t, cost in e: -            if dist[v] != INF and dist[v] + cost < dist[t]: -                dist[t] = dist[v] + cost -                update = 1 -    if not update: -        break + + +def SPFA(N, G, s): +    dist = [INF] * N +    cont = [0] * N +    cnts = [0] * N +    dist[s] = 0 +    cont[s] = 1 +    cnts[s] += 1 +    que = deque([s]) +    su = s +    num = 1 +    while que: +        v = que.popleft() +        cont[v] = 0 +        d = dist[v] +        su -= d +        num -= 1 +        for w, c in G[v]: +            r = d + c +            if r < dist[w]: +                if not cont[w]: +                    cnts[w] += 1 +                    if N <= cnts[w]: +                        return None +                    if que and r < que[0]: +                        que.appendleft(w) +                    else: +                        que.append(w) +                    cont[w] = 1 +                    su += r +                    num += 1 +                    dist[w] = r +                    while su < dist[que[0]] * num: +                        que.append(que.popleft()) +                else: +                    su += r - dist[w] +                    dist[w] = r +    return dist + + +dist = SPFA(N, G, r) +if dist is None: +    print("NEGATIVE CYCLE") -    print("NEGATIVE CYCLE") -    exit(0) -for i in range(V): -    print(dist[i] if dist[i] < INF else "INF") +    for i in range(N): +        print((dist[i] if dist[i] < INF else "INF"))