import sys

from heapq import heappush, heappop





def bellman_ford(V, Edges, start):

    dis = {}

    

    for i in range(V): dis[i] = (1 << 30)

    

    dis[start] = 0

    

    for i in range(V):

        for a, b, w in Edges:

            if dis[a] != (1 << 30) and dis[a] + w < dis[b]:

                dis[b] = dis[a] + w

    

    for a, b, w in Edges:

        if dis[a] != (1 << 30) and dis[a] + w < dis[b]:

            return ('NEGATIVE CYCLE', dis)

    

    return ('No NEGATIVE CYCLE', dis)

    

    

if __name__ == '__main__':

    line = sys.stdin.readline()

    V, E, start = line.split()

    V, E, start = int(V), int(E), int(start)

    Es = []

    for i in range(E):

        line = sys.stdin.readline()

        a, b, w = line.split()

        a, b, w = int(a), int(b), int(w)

        Es.append((a,b,w))

        

    judge, dis = bellman_ford(V, Es, start)

    

    if judge == 'NEGATIVE CYCLE':

        sys.stdout.write(judge + '\n')

    else:

        for i in range(V):

            if dis[i] == (1 << 30):

                sys.stdout.write('INF\n')

            else:

                sys.stdout.write(str(dis[i]) + '\n')


from collections import defaultdict, deque

from heapq import heappush, heappop

from sys import stdin



class UnionFindSet:

	def __init__(self, nodes):

		self.fa = {}

		for n in nodes:

			self.fa[n] = n



	def find(self, x):

		if self.fa[x] == x:

			return x

		else:

			self.fa[x] = self.find(self.fa[x])

			return self.fa[x]



	def union(self, x, y):

		fx = self.find(x)

		fy = self.find(y)

		if fx == fy:

			return fx

		else:

			self.fa[fx] = fy

			return fy





"""

graph is a hash

graph["nodes"] is a list of all nodes in the graph

graph["edges"] is a list of all edges in the graph in (x, y, w) form

  - x is the first nodes

  - y is the second nodes

  - w is the weight of the edges

graph["relation"] is the graph relation of the graph

"""



def kruscal(graph):

	"kruscal minimum spanning tree algorithm"

	ufset = UnionFindSet(graph["nodes"])



	ret = 0



	for (x, y, w) in sorted(graph["edges"], key = lambda x: x[-1]):

		fx = ufset.find(x)

		fy = ufset.find(y)

		if fx != fy:

			ret += w

			ufset.union(fx, fy)

		else:

			pass

	return ret





def dijkstra(graph, root):

	"dijkstra algorithm for single source shortest algorithm"

	dis, vis = {}, {}

	for n in graph["nodes"]:

		dis[n] = 10 ** 9

		vis[n] = False



	heap = []

	dis[root] = 0

	heappush(heap, (0, root))



	while heap:

		_, n = heappop(heap)

		vis[n] = True

		for (y, w) in graph["adj"][n]:

			if not vis[y] and dis[n] + w < dis[y]:

				dis[y] = dis[n] + w

				heappush(heap, (dis[y], y))



	return dis



def belmanFord(graph, root):

	dis = {}

	for n in graph["nodes"]:

		dis[n] = 10 ** 9



	dis[root] = 0



	# update for n - 1 times

	for _ in range(len(graph["nodes"]) - 1):

		for (x, y, w) in graph["edges"]:

			if dis[x] + w < dis[y]:

				dis[y] = dis[x] + w



	connect = set([root])

	que = deque([root])



	while que:

		n = que.popleft()

		for (y, _) in graph["adj"][n]:

			if not y in connect:

				connect.add(y)

				que.append(y)



	dis["negcicle"] = False

	for (x, y, w) in graph["edges"]:

		if dis[x] + w < dis[y] and x in connect:

			dis["negcicle"] = True



	dis["con"] = connect

	return dis



if __name__ == '__main__':

	V, E, root = list(map(int, stdin.readline().strip().split()))

	graph = {}

	graph["nodes"] = [i for i in range(V)]

	graph["edges"] = []

	graph["adj"] = defaultdict(list)

	for _ in range(E):

		x, y, w = list(map(int, stdin.readline().strip().split()))

		graph["edges"].append((x, y, w))

		graph["adj"][x].append((y, w))



	dis = belmanFord(graph, root)



	if dis["negcicle"]:

		print("NEGATIVE CYCLE")

	else:

		for n in graph["nodes"]:

			print(dis[n] if dis[n] < 10 ** 9 and n in dis["con"] else "INF")
import sys
from heapq import heappush, heappop


def bellman_ford(V, Edges, start):
    dis = {}
    for i in range(V):
        dis[i] = 1 << 30
    dis[start] = 0
    for i in range(V):
        for a, b, w in Edges:
            if dis[a] != (1 << 30) and dis[a] + w < dis[b]:
                dis[b] = dis[a] + w
    for a, b, w in Edges:
        if dis[a] != (1 << 30) and dis[a] + w < dis[b]:
            return ("NEGATIVE CYCLE", dis)
    return ("No NEGATIVE CYCLE", dis)


if __name__ == "__main__":
    line = sys.stdin.readline()
    V, E, start = line.split()
    V, E, start = int(V), int(E), int(start)
    Es = []
    for i in range(E):
        line = sys.stdin.readline()
        a, b, w = line.split()
        a, b, w = int(a), int(b), int(w)
        Es.append((a, b, w))
    judge, dis = bellman_ford(V, Es, start)
    if judge == "NEGATIVE CYCLE":
        sys.stdout.write(judge + "\n")
    else:
        for i in range(V):
            if dis[i] == (1 << 30):
                sys.stdout.write("INF\n")
            else:
                sys.stdout.write(str(dis[i]) + "\n")

from collections import defaultdict, deque
from heapq import heappush, heappop
from sys import stdin


class UnionFindSet:
    def __init__(self, nodes):
        self.fa = {}
        for n in nodes:
            self.fa[n] = n

    def find(self, x):
        if self.fa[x] == x:
            return x
        else:
            self.fa[x] = self.find(self.fa[x])
            return self.fa[x]

    def union(self, x, y):
        fx = self.find(x)
        fy = self.find(y)
        if fx == fy:
            return fx
        else:
            self.fa[fx] = fy
            return fy


"""
graph is a hash
graph["nodes"] is a list of all nodes in the graph
graph["edges"] is a list of all edges in the graph in (x, y, w) form
  - x is the first nodes
  - y is the second nodes
  - w is the weight of the edges
graph["relation"] is the graph relation of the graph
"""


def kruscal(graph):
    "kruscal minimum spanning tree algorithm"
    ufset = UnionFindSet(graph["nodes"])
    ret = 0
    for (x, y, w) in sorted(graph["edges"], key=lambda x: x[-1]):
        fx = ufset.find(x)
        fy = ufset.find(y)
        if fx != fy:
            ret += w
            ufset.union(fx, fy)
        else:
            pass
    return ret


def dijkstra(graph, root):
    "dijkstra algorithm for single source shortest algorithm"
    dis, vis = {}, {}
    for n in graph["nodes"]:
        dis[n] = 10**9
        vis[n] = False
    heap = []
    dis[root] = 0
    heappush(heap, (0, root))
    while heap:
        _, n = heappop(heap)
        vis[n] = True
        for (y, w) in graph["adj"][n]:
            if not vis[y] and dis[n] + w < dis[y]:
                dis[y] = dis[n] + w
                heappush(heap, (dis[y], y))
    return dis


def belmanFord(graph, root):
    dis = {}
    for n in graph["nodes"]:
        dis[n] = 10**9
    dis[root] = 0
    # update for n - 1 times
    for _ in range(len(graph["nodes"]) - 1):
        for (x, y, w) in graph["edges"]:
            if dis[x] + w < dis[y]:
                dis[y] = dis[x] + w
    connect = set([root])
    que = deque([root])
    while que:
        n = que.popleft()
        for (y, _) in graph["adj"][n]:
            if not y in connect:
                connect.add(y)
                que.append(y)
    dis["negcicle"] = False
    for (x, y, w) in graph["edges"]:
        if dis[x] + w < dis[y] and x in connect:
            dis["negcicle"] = True
    dis["con"] = connect
    return dis


if __name__ == "__main__":
    V, E, root = list(map(int, stdin.readline().strip().split()))
    graph = {}
    graph["nodes"] = [i for i in range(V)]
    graph["edges"] = []
    graph["adj"] = defaultdict(list)
    for _ in range(E):
        x, y, w = list(map(int, stdin.readline().strip().split()))
        graph["edges"].append((x, y, w))
        graph["adj"][x].append((y, w))
    dis = belmanFord(graph, root)
    if dis["negcicle"]:
        print("NEGATIVE CYCLE")
    else:
        for n in graph["nodes"]:
            print(dis[n] if dis[n] < 10**9 and n in dis["con"] else "INF")

-import sys +from collections import defaultdict, deque +from sys import stdin -def bellman_ford(V, Edges, start): +class UnionFindSet: +    def __init__(self, nodes): +        self.fa = {} +        for n in nodes: +            self.fa[n] = n + +    def find(self, x): +        if self.fa[x] == x: +            return x +        else: +            self.fa[x] = self.find(self.fa[x]) +            return self.fa[x] + +    def union(self, x, y): +        fx = self.find(x) +        fy = self.find(y) +        if fx == fy: +            return fx +        else: +            self.fa[fx] = fy +            return fy + + +""" +graph is a hash +graph["nodes"] is a list of all nodes in the graph +graph["edges"] is a list of all edges in the graph in (x, y, w) form +  - x is the first nodes +  - y is the second nodes +  - w is the weight of the edges +graph["relation"] is the graph relation of the graph +""" + + +def kruscal(graph): +    "kruscal minimum spanning tree algorithm" +    ufset = UnionFindSet(graph["nodes"]) +    ret = 0 +    for (x, y, w) in sorted(graph["edges"], key=lambda x: x[-1]): +        fx = ufset.find(x) +        fy = ufset.find(y) +        if fx != fy: +            ret += w +            ufset.union(fx, fy) +        else: +            pass +    return ret + + +def dijkstra(graph, root): +    "dijkstra algorithm for single source shortest algorithm" +    dis, vis = {}, {} +    for n in graph["nodes"]: +        dis[n] = 10**9 +        vis[n] = False +    heap = [] +    dis[root] = 0 +    heappush(heap, (0, root)) +    while heap: +        _, n = heappop(heap) +        vis[n] = True +        for (y, w) in graph["adj"][n]: +            if not vis[y] and dis[n] + w < dis[y]: +                dis[y] = dis[n] + w +                heappush(heap, (dis[y], y)) +    return dis + + +def belmanFord(graph, root): -    for i in range(V): -        dis[i] = 1 << 30 -    dis[start] = 0 -    for i in range(V): -        for a, b, w in Edges: -            if dis[a] != (1 << 30) and dis[a] + w < dis[b]: -                dis[b] = dis[a] + w -    for a, b, w in Edges: -        if dis[a] != (1 << 30) and dis[a] + w < dis[b]: -            return ("NEGATIVE CYCLE", dis) -    return ("No NEGATIVE CYCLE", dis) +    for n in graph["nodes"]: +        dis[n] = 10**9 +    dis[root] = 0 +    # update for n - 1 times +    for _ in range(len(graph["nodes"]) - 1): +        for (x, y, w) in graph["edges"]: +            if dis[x] + w < dis[y]: +                dis[y] = dis[x] + w +    connect = set([root]) +    que = deque([root]) +    while que: +        n = que.popleft() +        for (y, _) in graph["adj"][n]: +            if not y in connect: +                connect.add(y) +                que.append(y) +    dis["negcicle"] = False +    for (x, y, w) in graph["edges"]: +        if dis[x] + w < dis[y] and x in connect: +            dis["negcicle"] = True +    dis["con"] = connect +    return dis -    line = sys.stdin.readline() -    V, E, start = line.split() -    V, E, start = int(V), int(E), int(start) -    Es = [] -    for i in range(E): -        line = sys.stdin.readline() -        a, b, w = line.split() -        a, b, w = int(a), int(b), int(w) -        Es.append((a, b, w)) -    judge, dis = bellman_ford(V, Es, start) -    if judge == "NEGATIVE CYCLE": -        sys.stdout.write(judge + "\n") +    V, E, root = list(map(int, stdin.readline().strip().split())) +    graph = {} +    graph["nodes"] = [i for i in range(V)] +    graph["edges"] = [] +    graph["adj"] = defaultdict(list) +    for _ in range(E): +        x, y, w = list(map(int, stdin.readline().strip().split())) +        graph["edges"].append((x, y, w)) +        graph["adj"][x].append((y, w)) +    dis = belmanFord(graph, root) +    if dis["negcicle"]: +        print("NEGATIVE CYCLE") -        for i in range(V): -            if dis[i] == (1 << 30): -                sys.stdout.write("INF\n") -            else: -                sys.stdout.write(str(dis[i]) + "\n") +        for n in graph["nodes"]: +            print(dis[n] if dis[n] < 10**9 and n in dis["con"] else "INF")