from collections import defaultdict

import heapq



vertice,edge,source = list(map(int,input().split(" ")))

link = defaultdict(dict)

weight = defaultdict(dict)

cost = [float("inf") for n in range(vertice)]

cost[source] = 0

for e in range(edge):

    i,j,w = list(map(int,input().split(" ")))

    link[i] = link.get(i,set()) | {j}

    weight[i].update({j:w})



vertice_cnt = 0

while True:

    if vertice_cnt >= vertice:

        print("NEGATIVE CYCLE")

        break

    update = False

    for k,val in list(link.items()):

        for v in val:

            if cost[v] > cost[k] + weight[k][v]:

                cost[v] = cost[k] + weight[k][v]

                update = True

    if not(update):

        for c in cost:

            print((c if c != float("inf") else "INF"))

        break

    vertice_cnt += 1
from collections import defaultdict

v_num, e_num, source = (int(n) for n in input().split(" "))

conn = []

cost = [float("inf") for n in range(v_num)]

cost[source] = 0

for _ in range(e_num):

    s1, t1, weight = (int(n) for n in input().split(" "))

    conn.append([s1, t1, weight])



def bellman_ford(source, conn, v_num, cost):

    for i in range(v_num):

        for s, t, weight in conn:

            if cost[t] > cost[s] + weight:

                if i == v_num - 1:

                    return True

                cost[t] = cost[s] + weight

    return False



if bellman_ford(source, conn, v_num, cost):

    print("NEGATIVE CYCLE")

else:

    cost = ["INF" if n == float("inf") else n for n in cost]

    for c in cost:

        print(c)
from collections import defaultdict
import heapq

vertice, edge, source = list(map(int, input().split(" ")))
link = defaultdict(dict)
weight = defaultdict(dict)
cost = [float("inf") for n in range(vertice)]
cost[source] = 0
for e in range(edge):
    i, j, w = list(map(int, input().split(" ")))
    link[i] = link.get(i, set()) | {j}
    weight[i].update({j: w})
vertice_cnt = 0
while True:
    if vertice_cnt >= vertice:
        print("NEGATIVE CYCLE")
        break
    update = False
    for k, val in list(link.items()):
        for v in val:
            if cost[v] > cost[k] + weight[k][v]:
                cost[v] = cost[k] + weight[k][v]
                update = True
    if not (update):
        for c in cost:
            print((c if c != float("inf") else "INF"))
        break
    vertice_cnt += 1

from collections import defaultdict

v_num, e_num, source = (int(n) for n in input().split(" "))
conn = []
cost = [float("inf") for n in range(v_num)]
cost[source] = 0
for _ in range(e_num):
    s1, t1, weight = (int(n) for n in input().split(" "))
    conn.append([s1, t1, weight])


def bellman_ford(source, conn, v_num, cost):
    for i in range(v_num):
        for s, t, weight in conn:
            if cost[t] > cost[s] + weight:
                if i == v_num - 1:
                    return True
                cost[t] = cost[s] + weight
    return False


if bellman_ford(source, conn, v_num, cost):
    print("NEGATIVE CYCLE")
else:
    cost = ["INF" if n == float("inf") else n for n in cost]
    for c in cost:
        print(c)

-import heapq -vertice, edge, source = list(map(int, input().split(" "))) -link = defaultdict(dict) -weight = defaultdict(dict) -cost = [float("inf") for n in range(vertice)] +v_num, e_num, source = (int(n) for n in input().split(" ")) +conn = [] +cost = [float("inf") for n in range(v_num)] -for e in range(edge): -    i, j, w = list(map(int, input().split(" "))) -    link[i] = link.get(i, set()) | {j} -    weight[i].update({j: w}) -vertice_cnt = 0 -while True: -    if vertice_cnt >= vertice: -        print("NEGATIVE CYCLE") -        break -    update = False -    for k, val in list(link.items()): -        for v in val: -            if cost[v] > cost[k] + weight[k][v]: -                cost[v] = cost[k] + weight[k][v] -                update = True -    if not (update): -        for c in cost: -            print((c if c != float("inf") else "INF")) -        break -    vertice_cnt += 1 +for _ in range(e_num): +    s1, t1, weight = (int(n) for n in input().split(" ")) +    conn.append([s1, t1, weight]) + + +def bellman_ford(source, conn, v_num, cost): +    for i in range(v_num): +        for s, t, weight in conn: +            if cost[t] > cost[s] + weight: +                if i == v_num - 1: +                    return True +                cost[t] = cost[s] + weight +    return False + + +if bellman_ford(source, conn, v_num, cost): +    print("NEGATIVE CYCLE") +else: +    cost = ["INF" if n == float("inf") else n for n in cost] +    for c in cost: +        print(c)