Constraints

* 1 ≤ |V| ≤ 1000
* 0 ≤ |E| ≤ 2000
* -10000 ≤ di ≤ 10000
* There are no parallel edges
* There are no self-loops

Input

An edge-weighted graph G (V, E) and the source r.


|V| |E| r
s0 t0 d0
s1 t1 d1
:
s|E|-1 t|E|-1 d|E|-1


|V| is the number of vertices and |E| is the number of edges in G. The graph vertices are named with the numbers 0, 1,..., |V|-1 respectively. r is the source of the graph.

si and ti represent source and target vertices of i-th edge (directed) and di represents the cost of the i-th edge.

Output

If the graph contains a negative cycle (a cycle whose sum of edge costs is a negative value) which is reachable from the source r, print


NEGATIVE CYCLE


in a line.

Otherwise, print


c0
c1
:
c|V|-1


The output consists of |V| lines. Print the cost of the shortest path from the source r to each vertex 0, 1, ... |V|-1 in order. If there is no path from the source to a vertex, print "INF".

Examples

Input

4 5 0
0 1 2
0 2 3
1 2 -5
1 3 1
2 3 2


Output

0
2
-3
-1


Input

4 6 0
0 1 2
0 2 3
1 2 -5
1 3 1
2 3 2
3 1 0


Output

NEGATIVE CYCLE


Input

4 5 1
0 1 2
0 2 3
1 2 -5
1 3 1
2 3 2


Output

INF
0
-5
-3

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
import collections
import sys
sys.setrecursionlimit(100000)
(V_num, E_num, r) = [int(ele) for ele in input().split()]
adjc_list = []
edges = []
for _ in range(V_num):
	adjc_list.append([])
for _ in range(E_num):
	(src, dst, w) = [int(ele) for ele in input().split()]
	adjc_list[src].append([w, dst])
	edges.append([src, dst, w])
INF = 99999999999999
d = [INF for _ in range(V_num)]
d[r] = 0
stack = collections.deque()
yet = [ele for ele in range(V_num)]

def main():
	global edges
	stack.clear()
	stack.appendleft(r)
	dfs(stack)
	edges = list(filter(lambda e: e[0] not in yet and e[1] not in yet, edges))
	output_ans() if bellman_ford() != -1 else print('NEGATIVE CYCLE')

def dfs(stack):
	if not stack:
		return
	n = stack[0]
	yet.remove(n)
	for (_, dst) in adjc_list[n]:
		if dst in yet:
			stack.appendleft(dst)
			dfs(stack)
	else:
		stack.popleft()

def bellman_ford():
	for _ in range(V_num - 1):
		for (src, dst, w) in edges:
			if d[dst] > w + d[src]:
				d[dst] = w + d[src]
	for (src, dst, w) in edges:
		if d[dst] > w + d[src]:
			return -1
	return

def output_ans():
	for d_i in d:
		if d_i == INF:
			print('INF')
		else:
			print(d_i)
main()


import sys
file_input = sys.stdin
(V, E, r) = map(int, file_input.readline().split())
edges = []
for line in file_input:
	edges.append(tuple(map(int, line.split())))
distance = [float('inf')] * V
distance[r] = 0
for i in range(V):
	notUpdated = True
	for e in edges:
		t = e[1]
		temp_d = distance[e[0]] + e[2]
		if temp_d < distance[t]:
			distance[t] = temp_d
			notUpdated = False
	if notUpdated:
		break
if i == V - 1 and V != 1:
	print('NEGATIVE CYCLE')
else:
	print(*map(lambda x: str(x).upper(), distance), sep='\n')


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, copy, functools
import time, random
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
mod2 = 998244353
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI():
	return [list(map(int, l.split())) for l in sys.stdin.readlines()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def pe(s):
	return print(str(s), file=sys.stderr)

def JA(a, sep):
	return sep.join(map(str, a))

def JAA(a, s, t):
	return s.join((t.join(map(str, b)) for b in a))

class BellmanFord:

	def __init__(self, n):
		self.N = n
		self.e = collections.defaultdict(list)

	def add(self, u, v, d):
		self.e[u].append((v, d))

	def delete(self, u, v):
		self.e[u] = [_ for _ in self.e[u] if _[0] != v]

	def search(self, s):
		d = collections.defaultdict(lambda : inf)
		d[s] = 0
		update = True
		cnt = 0
		while update:
			cnt += 1
			if cnt > self.N:
				return (d, True)
			update = False
			for (k, v) in self.e.items():
				if d[k] == inf:
					continue
				dk = d[k]
				for (n, nd) in v:
					if d[n] > dk + nd:
						update = True
						d[n] = dk + nd
		return (d, False)

	def search(s, N):
		d = collections.defaultdict(lambda : inf)
		d[s] = 0
		update = True
		cnt = 0
		while update:
			cnt += 1
			if cnt > N:
				return (d, True)
			update = False
			for (k, v) in e.items():
				if d[k] == inf:
					continue
				dk = d[k]
				for (n, nd) in v:
					if d[n] > dk + nd:
						update = True
						d[n] = dk + nd
		return (d, False)

def main():
	(v, e, r) = LI()
	std = [LI() for _ in range(e)]
	e = collections.defaultdict(list)
	for (s, t, d) in std:
		e[s].append((t, d))

	def search(s, N):
		d = collections.defaultdict(lambda : inf)
		d[s] = 0
		us = set([s])
		cnt = 0
		while us:
			cnt += 1
			if cnt > N:
				return (d, True)
			ns = set()
			for (k, v) in e.items():
				if d[k] == inf:
					continue
				dk = d[k]
				for (n, nd) in v:
					if d[n] > dk + nd:
						ns.add(n)
						d[n] = dk + nd
			us = ns
		return (d, False)
	(d, f) = search(r, v)
	if f:
		return 'NEGATIVE CYCLE'
	r = []
	for i in range(v):
		t = d[i]
		if t == inf:
			r.append('INF')
		else:
			r.append(t)
	return JA(r, '\n')
print(main())


import sys
inf = 1 << 60

def solve():
	(N, M, r) = map(int, sys.stdin.readline().split())
	edges = [None] * M
	for i in range(M):
		(si, ti, di) = map(int, sys.stdin.readline().split())
		edges[i] = (si, ti, di)
	ans = BellmanFord(N, M, edges, r)
	print(*ans, sep='\n')

def BellmanFord(N, M, edges, r):
	d = [inf] * N
	d[r] = 0
	for i in range(N):
		flag = False
		for (u, v, c) in edges:
			if d[u] != inf and d[u] + c < d[v]:
				d[v] = d[u] + c
				flag = True
		if flag and i == N - 1:
			return ['NEGATIVE CYCLE']
	d = [di if di < inf else 'INF' for di in d]
	return d
solve()


class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = [-1 for i in range(n + 1)]

	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.parents[x] > self.parents[y]:
			(x, y) = (y, x)
		self.parents[x] += self.parents[y]
		self.parents[y] = x

	def size(self, x):
		return -self.parents[self.find(x)]

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def members(self, x):
		root = self.find(x)
		return [i for i in range(self.n + 1) if self.find(i) == root]

	def roots(self):
		return [i for (i, x) in enumerate(self.parents) if x < 0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		return {r: self.members(r) for r in self.roots()}

	def __str__(self):
		return '\n'.join(('{}: {}'.format(r, self.members(r)) for r in self.roots()))

class Graph:

	def __init__(self, N, Type):
		self._V = N
		self._E = 0
		self.type = Type
		if Type == 'D':
			self.G = [[] for i in range(self._V + 1)]
		elif Type == 'W':
			self.G = [[float('inf') for i in range(self._V + 1)] for j in range(self._V + 1)]
		elif Type == 'B' or Type == 'K':
			self.G = []

	def E(self):
		return self._E

	@property
	def V(self):
		return self._V

	def add(self, _from, _to, _cost):
		self._E += 1
		if self.type == 'D':
			self.G[_from].append((_to, _cost))
		elif self.type == 'W':
			self.G[_from][_to] = _cost
		elif self.type == 'B' or self.type == 'K':
			self.G.append((_from, _to, _cost))

	def add_both(self, _from, _to, _cost):
		self.add(_from, _to, _cost)
		self.add(_to, _from, _cost)

class Bellman_Ford(Graph):

	def __init__(self, N):
		super().__init__(N, 'B')
		self.d = [float('inf')] * (self._V + 1)

	def shortest_path(self, s):
		self.d[s] = 0
		for _ in range(self._V):
			flag = False
			for (From, To, cost) in self.G:
				newlen = self.d[From] + cost
				if newlen < self.d[To]:
					flag = True
					self.d[To] = newlen
			if not flag:
				break
		return self.d

	def have_negative_circle(self, s):
		self.d[s] = 0
		for i in range(1, self._V + 1):
			flag = False
			for (From, To, cost) in self.G:
				newlen = self.d[From] + cost
				if newlen < self.d[To]:
					flag = True
					self.d[To] = newlen
			if not flag:
				break
			if i == self._V:
				return False
		return self.d

def main():
	(V, E, r) = map(int, input().split())
	r += 1
	G = Bellman_Ford(V)
	for i in range(E):
		(s, t, d) = map(int, input().split())
		s += 1
		t += 1
		G.add(s, t, d)
	result = G.have_negative_circle(r)
	if result == False:
		print('NEGATIVE CYCLE')
		return
	else:
		for i in range(1, V + 1):
			if result[i] == float('inf'):
				print('INF')
			else:
				print(result[i])
		return
main()


inf = float('inf')

class Bellmanford:

	def __init__(self, to: list, start: int, goal: int):
		self.N = len(to)
		self.to = [s[:] for s in to]
		self.start = start
		self.goal = goal
		self.dist = [inf] * self.N
		self.dist[start] = 0
		self.exists_negative_cycle = False
		self.exists_negative_cycle_stog = False
		self.is_updated = [False] * self.N

	def update(self) -> None:
		for _ in range(self.N - 1):
			for (v, s) in enumerate(self.to):
				if not s:
					continue
				for (nv, w) in s:
					if self.dist[nv] > self.dist[v] + w:
						self.dist[nv] = self.dist[v] + w

	def detection(self) -> bool:
		for (v, s) in enumerate(self.to):
			if not s:
				continue
			for (nv, w) in s:
				if self.dist[nv] > self.dist[v] + w:
					self.dist[nv] = self.dist[v] + w
					self.exists_negative_cycle = True
		return self.exists_negative_cycle

	def detection_stog(self) -> bool:
		for _ in range(self.N):
			for (v, s) in enumerate(self.to):
				if not s:
					continue
				for (nv, w) in s:
					if self.dist[nv] > self.dist[v] + w:
						self.dist[nv] = self.dist[v] + w
						self.is_updated[nv] = True
					if self.is_updated[v] is True:
						self.is_updated[nv] = True
		self.exists_negative_cycle_stog = self.is_updated[self.goal]
		return self.exists_negative_cycle_stog
(N, M, r) = map(int, input().split())
to = [[] for _ in range(N)]
for _ in range(M):
	(s, t, d) = map(int, input().split())
	to[s].append((t, d))
BF = Bellmanford(to, r, -1)
BF.update()
if BF.detection():
	print('NEGATIVE CYCLE')
else:
	for d in BF.dist:
		if d == inf:
			print('INF')
		else:
			print(d)


(V, E, r) = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(E)]
dist = [float('inf') for _ in range(V)]
dist[r - 1] = 0
for i in range(V + 1):
	for edge in edges:
		if edge[0] != float('inf') and dist[edge[1] - 1] > dist[edge[0] - 1] + edge[2]:
			dist[edge[1] - 1] = dist[edge[0] - 1] + edge[2]
			if i == V - 1:
				print('NEGATIVE CYCLE')
				exit()
print('\n'.join((str(dist[e - 1]) if dist[e - 1] != float('inf') else 'INF' for e in range(V))))


from math import isinf

def main():
	(V, E, r) = map(int, input().split())
	vertices = [float('inf')] * V
	vertices[r] = 0
	edges = []
	for i in range(E):
		(s, t, d) = map(int, input().split())
		edges.append((s, t, d))
	for i in range(V - 1):
		for (s, t, d) in edges:
			if vertices[t] > vertices[s] + d:
				vertices[t] = vertices[s] + d
	for (s, t, d) in edges:
		if vertices[t] > vertices[s] + d:
			print('NEGATIVE CYCLE')
			return
	for v in vertices:
		print('INF' if isinf(v) else v)
main()


from sys import stdin
from collections import deque
(V, E, R) = [int(x) for x in stdin.readline().split()]
d = {}
tick = False
INF = float('inf')
for i in range(V):
	d[i] = INF
d[R] = 0
weight = {}
st = []
for i in range(1, V + 1):
	for j in range(E):
		if i == 1:
			(s, t, w) = [int(x) for x in stdin.readline().split()]
			weight[s, t] = w
			st.append((s, t))
		(s, t) = st[j]
		if d[t] > d[s] + weight[s, t]:
			d[t] = d[s] + weight[s, t]
			if i == V:
				print('NEGATIVE CYCLE')
				quit()
for k in range(V):
	if d[k] == float('inf'):
		print('INF')
	else:
		print(d[k])


from collections import namedtuple
WEIGHT_MAX = 10 ** 10
WeightedEdge = namedtuple('WeightedEdge', ('src', 'dest', 'weight'))

class Digraph:

	def __init__(self, v):
		self.v = v
		self.edges = [[] for _ in range(v)]

	def add(self, edge):
		self.edges[edge.src].append(edge)

	def adj(self, v):
		return self.edges[v]

def sp_bellmanford(graph, s):

	def relax(edge):
		(s, t, w) = edge
		if dists[t] > dists[s] + w:
			dists[t] = dists[s] + w
			srcs[t] = s
			_nodes.append(t)
	dists = [WEIGHT_MAX] * graph.v
	dists[s] = 0
	srcs = [-1] * graph.v
	nodes = []
	nodes.append(s)
	for _ in range(graph.v):
		_nodes = []
		for v in nodes:
			for e in graph.adj(v):
				relax(e)
		nodes = _nodes
	if len(nodes) > 0:
		return None
	else:
		return [None if dists[v] == WEIGHT_MAX else dists[v] for v in range(graph.v)]

def run():
	(v, e, r) = [int(i) for i in input().split()]
	graph = Digraph(v)
	for _ in range(e):
		edge = WeightedEdge(*[int(i) for i in input().split()])
		graph.add(edge)
	ws = sp_bellmanford(graph, r)
	if ws is None:
		print('NEGATIVE CYCLE')
	else:
		for w in ws:
			if w is None:
				print('INF')
			else:
				print('{:d}'.format(w))
run()


import sys
INF = float('inf')

def Bellmanford(n, edges, r):
	d = [INF] * n
	d[r] = 0
	for i in range(n):
		flag = False
		for (u, v, c) in edges:
			if d[u] != INF and d[u] + c < d[v]:
				d[v] = d[u] + c
				flag = True
		if flag and i == n - 1:
			return ['NEGATIVE CYCLE']
	d = [di if di < INF else 'INF' for di in d]
	return d
(V, E, R) = map(int, sys.stdin.readline().split())
Edges = [None] * E
for i in range(E):
	(si, ti, di) = map(int, sys.stdin.readline().split())
	Edges[i] = (si, ti, di)
ans = Bellmanford(V, Edges, R)
print(*ans, sep='\n')


def BellmanFord(edges, num_v, source):
	inf = float('inf')
	dist = [inf for i in range(num_v)]
	dist[source] = 0
	for i in range(num_v):
		for edge in edges:
			if dist[edge[0]] != inf and dist[edge[1]] > dist[edge[0]] + edge[2]:
				dist[edge[1]] = dist[edge[0]] + edge[2]
				if i == num_v - 1:
					return -1
	return dist
(V, E, r) = map(int, input().split())
STD = [list(map(int, input().split())) for i in range(E)]
inf = float('inf')
dist = BellmanFord(STD, V, r)
if dist == -1:
	print('NEGATIVE CYCLE')
else:
	for d in dist:
		if d == inf:
			print('INF')
		else:
			print(d)


import sys
inf = sys.maxsize * 1000000
(V, e, r) = (int(i) for i in input().split())
NC = False
G = []
for j in range(e):
	(f, t, cost) = (int(i) for i in input().split())
	G.append((f, t, cost))
dist = [inf for _ in range(100000)]
dist[r] = 0
max_ = 0
for i in range(V):
	for (u, v, cost) in G:
		if dist[u] != inf and dist[u] + cost < dist[v]:
			if i == V - 1:
				NC = True
			else:
				dist[v] = dist[u] + cost
if not NC:
	for i in range(V):
		if dist[i] >= inf / 2:
			print('INF')
		else:
			print(dist[i])
else:
	print('NEGATIVE CYCLE')


def main():
	from heapq import heappop, heappush
	INF = 1 << 30
	(n, m, r, *E) = map(int, open(0).read().split())
	G = [[] for _ in [0] * n]
	for (s, t, w) in zip(*[iter(E)] * 3):
		G[s].append((t, w))
	D = [INF] * n
	count = [0] * n
	in_queue = [False] * n
	q = []
	D[r] = 0
	count[r] = 1
	in_queue[r] = True
	heappush(q, (0, r))
	while q:
		(_, s) = heappop(q)
		in_queue[s] = False
		for (t, w) in G[s]:
			new_d = D[s] + w
			if new_d >= D[t]:
				continue
			D[t] = new_d
			count[t] += 1
			if count[t] >= n:
				print('NEGATIVE CYCLE')
				exit()
			if not in_queue[t]:
				in_queue[t] = True
				heappush(q, (new_d, t))
	print(*['INF' if d == INF else d for d in D], sep='\n')
main()


class BellmanFord:

	def __init__(self, V, E, start, INF=10 ** 9):
		self.V = V
		self.E = E
		self.bellman_ford(start, INF)

	def bellman_ford(self, start, INF):
		self.distance = [INF] * self.V
		self.prev = [-1] * self.V
		self.distance[start] = 0
		self.negativeCycle = False
		for i in range(V):
			update = False
			for v in range(V):
				for (to, cost) in self.E[v]:
					if self.distance[v] != INF and self.distance[v] + cost < self.distance[to]:
						self.distance[to] = self.distance[v] + cost
						self.prev[to] = v
						update = True
						if i == V - 1:
							self.negativeCycle = True
			if update == False:
				break

	def getPath(self, end):
		assert self.hasNegativeCycle() == False
		path = [end]
		while self.prev[end] != -1:
			end = self.prev[end]
		return path[::-1]

	def hasNegativeCycle(self):
		return self.negativeCycle
(V, E, r) = map(int, input().split())
INF = 10 ** 9
edge = [[] for _ in range(V)]
for _ in range(E):
	(s, t, d) = map(int, input().split())
	edge[s].append((t, d))
sp = BellmanFord(V, edge, r, INF)
if sp.hasNegativeCycle():
	print('NEGATIVE CYCLE')
else:
	for dist in sp.distance:
		print(dist if dist != INF else 'INF')


import sys
file_input = sys.stdin
(V, E, r) = map(int, file_input.readline().split())
edges = []
for line in file_input:
	edges.append(tuple(map(int, line.split())))
distance = [float('inf')] * V
distance[r] = 0
notUpdated = True
for i in range(V - 1):
	notUpdated = True
	for (s, t, w) in edges:
		temp_d = distance[s] + w
		if temp_d < distance[t]:
			distance[t] = temp_d
			notUpdated = False
	if notUpdated:
		break
if notUpdated:
	print(*map(lambda x: str(x).upper(), distance), sep='\n')
else:
	flag = True
	for (s, t, w) in edges:
		temp_d = distance[s] + w
		if temp_d < distance[t]:
			print('NEGATIVE CYCLE')
			flag = False
			break
	if flag:
		print(*map(lambda x: str(x).upper(), distance), sep='\n')


INF = 10 ** 18
(n, m, r) = map(int, input().split())
d = [INF] * n
d[r] = 0
p = [False] * n
p[r] = True
e = [None] * m
for i in range(m):
	e[i] = tuple(map(int, input().split()))
for _ in range(n):
	flg = 1
	for (s, t, da) in e:
		if p[s] == True and d[t] > d[s] + da:
			d[t] = d[s] + da
			p[t] = True
			flg = 0
	if flg:
		break
else:
	print('NEGATIVE CYCLE')
	exit(0)
for x in d:
	if x >= 10 ** 10:
		print('INF')
	else:
		print(x)


def shortest_path_faster_algorithm(E, start):
	from collections import deque
	inf = float('inf')
	N = len(E)
	q = deque([start])
	distance = [inf] * N
	distance[start] = 0
	in_q = [0] * N
	in_q[start] = True
	times = [0] * N
	times[start] = 1
	while q:
		v = q.popleft()
		in_q[v] = False
		dist_v = distance[v]
		for (u, cost) in E[v]:
			new_dist_u = dist_v + cost
			if distance[u] > new_dist_u:
				times[u] += 1
				if times[u] >= N:
					print('NEGATIVE CYCLE')
					exit()
					distance[u] = -inf
				else:
					distance[u] = new_dist_u
				if not in_q[u]:
					in_q[u] = True
					q.append(u)
	return distance
import sys

def main():
	(N, M, r) = map(int, sys.stdin.readline().split())
	E = [[] for _ in range(N)]
	for (s, t, d) in zip(*[iter(map(int, sys.stdin.read().split()))] * 3):
		E[s].append((t, d))
	distance = shortest_path_faster_algorithm(E, r)
	for d in distance:
		if d == float('inf'):
			print('INF')
		else:
			print(d)
main()


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

class Edge:

	def __init__(self, f, t, cost):
		self.f = f
		self.t = t
		self.cost = cost

def bellman_ford(s):
	dist[s] = 0
	for i in range(V):
		for j in range(E):
			e = G[j]
			if dist[e.f] < INF and dist[e.f] + e.cost < dist[e.t]:
				dist[e.t] = dist[e.f] + e.cost
				if i == V - 1:
					return True
	return False

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


def bellman_ford(s):
	d = [float('inf')] * n
	d[s] = 0
	for i in range(n):
		update = False
		for (x, y, z) in g:
			if d[y] > d[x] + z:
				d[y] = d[x] + z
				update = True
		if not update:
			break
		if i == n - 1:
			return -1
	return d
(n, w, s) = [int(x) for x in input().split()]
g = []
for _ in range(w):
	(x, y, z) = [int(x) for x in input().split()]
	g.append([x, y, z])
d = bellman_ford(s)
if d == -1:
	print('NEGATIVE CYCLE')
else:
	for i in d:
		if i == float('inf'):
			print('INF')
		else:
			print(i)


INF = float('inf')
edges = []
(V, E, r) = map(int, input().split())
for i in range(E):
	(s, t, d) = map(int, input().split())
	edges.append({'s': s, 't': t, 'd': d})
ds = [INF for i in range(V)]
ds[r] = 0
i = 0
while True:
	i = i + 1
	update = False
	for j in range(E):
		edge = edges[j]
		if ds[edge['s']] != INF and ds[edge['t']] > ds[edge['s']] + edge['d']:
			if i == V - 1:
				print('NEGATIVE CYCLE')
				exit()
			ds[edge['t']] = ds[edge['s']] + edge['d']
			update = True
	if not update:
		break
for i in range(V):
	print(ds[i] if ds[i] != INF else 'INF')


def main():
	(nvertices, nedges, s) = map(int, input().split())
	E = []
	for i in range(nedges):
		(u, v, w) = map(int, input().split())
		E.append((u, v, w))
	INF = 1000000000
	d = [INF] * nvertices
	d[s] = 0
	for i in range(nvertices - 1):
		for (u, v, w) in E:
			if d[u] == INF:
				continue
			if d[u] + w < d[v]:
				d[v] = d[u] + w
	for i in range(nvertices - 1):
		for (u, v, w) in E:
			if d[v] == INF:
				continue
			if d[v] > d[u] + w:
				print('NEGATIVE CYCLE')
				return
	for val in d:
		if val >= INF:
			print('INF')
		else:
			print(val)
main()


import sys
readline = sys.stdin.readline
(V, E, r) = map(int, readline().split())
inf = 10 ** 10
edges = [[] for _ in [None] * V]
for _ in [None] * E:
	(s, t, d) = map(int, readline().split())
	edges[s].append((t, d))

def bellman_ford(n, edges, start):
	vertices = [inf] * n
	vertices[start] = 0
	reached = {start}
	for i in range(n):
		flag = 0
		for v in reached.copy():
			cost = vertices[v]
			for (dist, _cost) in edges[v]:
				newcost = cost + _cost
				if vertices[dist] > newcost:
					vertices[dist] = newcost
					reached.add(dist)
					flag = 1
		if flag == 0:
			return vertices
	else:
		return None
result = bellman_ford(V, edges, r)
if result:
	print('\n'.join([str(n) if n != inf else 'INF' for n in result]))
else:
	print('NEGATIVE CYCLE')


def bellman_ford(s):
	dist = [float('inf')] * v
	dist[s] = 0
	for i in range(v):
		update = False
		for (p, q, cost) in edge:
			if dist[p] != float('inf') and dist[q] > dist[p] + cost:
				dist[q] = dist[p] + cost
				update = True
		if not update:
			break
		if i == v - 1:
			return False
	return dist
(v, e, r) = map(int, input().split())
edge = []
for _ in range(e):
	(s, t, d) = map(int, input().split())
	edge.append([s, t, d])
res = bellman_ford(r)
if not res:
	print('NEGATIVE CYCLE')
else:
	for v in res:
		if v == float('inf'):
			print('INF')
		else:
			print(v)


INF = float('inf')

def bellman_ford(graph, weights, s):
	d = {v: INF for v in graph}
	d[s] = 0
	edges = [(u, v) for (u, vs) in graph.items() for v in vs]
	for _ in range(len(graph) - 1):
		for (u, v) in edges:
			d_temp = d[u] + weights[u, v]
			if d_temp < d[v]:
				d[v] = d_temp
	for (u, v) in edges:
		if d[u] + weights[u, v] < d[v]:
			print('NEGATIVE CYCLE')
			return None
	return d
(n_vertex, n_edge, s) = [int(x) for x in input().split()]
graph = {i: [] for i in range(n_vertex)}
weights = {}
for i in range(n_edge):
	(u, v, w) = [int(x) for x in input().split()]
	graph[u].append(v)
	weights[u, v] = w
d = bellman_ford(graph, weights, s)
if d is not None:
	for i in range(n_vertex):
		print(d[i] if d[i] is not INF else 'INF')


from sys import stdin
from collections import deque
(V, E, R) = [int(x) for x in stdin.readline().split()]
d = {}
tick = False
INF = float('inf')
for i in range(V):
	d[i] = INF
d[R] = 0
weight = {}
st = deque([])
for i in range(1, V + 1):
	for j in range(E):
		if i == 1:
			(s, t, w) = [int(x) for x in stdin.readline().split()]
			weight[s, t] = w
			st.append((s, t))
		(s, t) = st.popleft()
		if d[t] > d[s] + weight[s, t]:
			d[t] = d[s] + weight[s, t]
			if i == V:
				print('NEGATIVE CYCLE')
				tick = True
				break
		st.append((s, t))
if not tick:
	for k in range(V):
		if d[k] == float('inf'):
			print('INF')
		else:
			print(d[k])


import sys
from sys import stdin
from collections import namedtuple
input = stdin.readline

def shortest_path(es, V, s):
	count = 0
	d = [float('inf')] * V
	d[s] = 0
	while True:
		update = False
		count += 1
		if count > V:
			return None
		for e in es:
			if d[e.f] != float('inf') and d[e.t] > d[e.f] + e.c:
				d[e.t] = d[e.f] + e.c
				update = True
		if update is False:
			break
	for (i, dist) in enumerate(d):
		if dist == float('inf'):
			d[i] = 'INF'
	return d
edge = namedtuple('edge', ['f', 't', 'c'])

def main(args):
	(V, E, r) = map(int, input().split())
	es = []
	for _ in range(E):
		(s, t, d) = map(int, input().split())
		es.append(edge(s, t, d))
	result = shortest_path(es, V, r)
	if result is None:
		print('NEGATIVE CYCLE')
	else:
		print('\n'.join(map(str, result)))
main(sys.argv[1:])


(v, e, r) = map(int, input().split())
g = [[] for _ in range(v)]
for i in range(e):
	(s, t, d) = map(int, input().split())
	g[s].append((d, t))
dist = [float('inf')] * v
dist[r] = 0
updated = False
for k in range(v - 1):
	updated = False
	for i in range(v):
		for j in g[i]:
			if dist[i] != float('inf') and dist[i] + j[0] < dist[j[1]]:
				dist[j[1]] = dist[i] + j[0]
				updated = True
	if not updated:
		break
if updated:
	print('NEGATIVE CYCLE')
	exit()
for i in dist:
	if i == float('inf'):
		print('INF')
	else:
		print(i)


(V, E, r) = map(int, input().split())
paths = []
for i in range(E):
	paths.append(list(map(int, input().split())))
INF = 10 ** 20
cost = [INF for x in range(V)]
cost[r] = 0
inf_flg = False
for i in range(V * 2):
	for p in paths:
		(f, t, c) = (p[0], p[1], p[2])
		if cost[t] > cost[f] + c and (not cost[t] == cost[f] == INF):
			cost[t] = cost[f] + c
			if i >= V:
				inf_flg = True
if inf_flg == True:
	print('NEGATIVE CYCLE')
else:
	for c in cost:
		if c == INF:
			print('INF')
		else:
			print(c)


import sys
from math import isinf

class Edge(object):
	__slots__ = ('source', 'target', 'cost')

	def __init__(self):
		self.cost = float('inf')
		(self.source, self.target) = (None, None)

def generate_edge_table(_v_info):
	for (index, each) in enumerate(_v_info):
		edge = init_edge_table[index]
		(source, target, cost) = map(int, each)
		edge.source = source
		edge.target = target
		edge.cost = cost
	return init_edge_table

def bellman_ford():
	distance[root] = 0
	for j in range(vertices - 1):
		for edge in edge_table:
			(source, target, cost) = (edge.source, edge.target, edge.cost)
			if distance[source] + cost < distance[target]:
				distance[target] = distance[source] + cost
	for edge in edge_table:
		(source, target, cost) = (edge.source, edge.target, edge.cost)
		if distance[source] + cost < distance[target]:
			print('NEGATIVE CYCLE')
			return list()
	return distance
_input = sys.stdin.readlines()
(vertices, edges, root) = map(int, _input[0].split())
v_info = map(lambda x: x.split(), _input[1:])
distance = [float('inf')] * vertices
init_edge_table = tuple((Edge() for _ in range(edges)))
edge_table = generate_edge_table(v_info)
res = bellman_ford()
if res:
	print('\n'.join(('INF' if isinf(ele) else str(ele) for ele in res)))


d = []
(v, e, r) = list(map(int, input().split()))
edges = [list(map(int, input().split())) for i in range(e)]

def bellman_ford(s):
	global d
	d = [float('inf') for i in range(v)]
	d[s] = 0
	for i in range(v - 1):
		for (s, t, w) in edges:
			if d[t] > d[s] + w:
				d[t] = d[s] + w
	for (s, t, w) in edges:
		if d[s] + w < d[t]:
			return False
	return True
if bellman_ford(r):
	for w in d:
		if w == float('inf'):
			print('INF')
		else:
			print(w)
else:
	print('NEGATIVE CYCLE')


(Vn, En, r) = map(int, input().split())
E = []
for _ in range(En):
	(s, t, c) = map(int, input().split())
	E.append((s, t, c))
INF = 10 ** 3 * 10 ** 4
dp = [INF * 10] * Vn
dp[r] = 0
for i in range(Vn):
	for (u, v, duv) in E:
		if dp[v] > dp[u] + duv:
			dp[v] = dp[u] + duv
for (u, v, c) in E:
	if dp[v] > INF:
		continue
	if dp[u] + c < dp[v]:
		print('NEGATIVE CYCLE')
		break
else:
	for i in range(Vn):
		if not dp[i] > 10 ** 3 * 10 ** 4:
			print(dp[i])
		else:
			print('INF')


import array
import collections
G_INF = 2 ** 31

class GraphError(Exception):
	pass

class GraphSearchError(GraphError):

	def __init__(self, reason):
		self.reason = reason

	def __str__(self):
		return str(reason)

class ShortestPathFasterAlgorithm(object):

	def __init__(self, number_of_vertices, adjacency_list, costs, start):
		self.max_v = number_of_vertices
		self.adj = adjacency_list
		self.costs = costs
		self.start = start
		self.dist = None
		self.visits = None

	def initialize(self):
		self.dist = collections.defaultdict(lambda : G_INF)
		self.dist[self.start] = 0
		self.visits = collections.defaultdict(int)

	def single_source_shortest_path(self):
		self.initialize()
		q = collections.deque()
		q.append(self.start)
		while q:
			u = q.popleft()
			self.visits[u] += 1
			if self.visits[u] >= self.max_v:
				if self.max_v == 1:
					return [0]
				raise GraphSearchError('A negative cycle was detected.')
			for v in self.adj[u]:
				new_length = self.dist[u] + self.costs[u, v]
				if new_length < self.dist[v]:
					self.dist[v] = new_length
					if v not in q:
						q.append(v)
		return self.dist

def main():
	(max_v, max_e, start) = map(int, input().split())
	adjacency_list = collections.defaultdict(lambda : array.array('L'))
	costs = collections.defaultdict(lambda : G_INF)
	for _ in range(max_e):
		(s, t, d) = map(int, input().split())
		adjacency_list[s].append(t)
		costs[s, t] = d
	spfa = ShortestPathFasterAlgorithm(max_v, adjacency_list, costs, start)
	try:
		dist = spfa.single_source_shortest_path()
		for v in range(max_v):
			result = dist[v]
			if result < G_INF:
				print(result)
			else:
				print('INF')
	except GraphSearchError as gse:
		print('NEGATIVE CYCLE')
main()


(v, e, r) = map(int, input().split())
D = [float('inf')] * v
L = []
find_negative = False
for i in range(e):
	(s, t, d) = map(int, input().split())
	L.append([s, t, d])
D[r] = 0
for i in range(v):
	update = False
	for j in range(e):
		(a, b, c) = (L[j][0], L[j][1], L[j][2])
		if D[b] > D[a] + c:
			D[b] = D[a] + c
			update = True
			if i == v - 1:
				find_negative = True
				break
	if not update:
		break
if find_negative:
	print('NEGATIVE CYCLE')
else:
	for i in range(v):
		if D[i] == float('inf'):
			print('INF')
		else:
			print(D[i])


import array
import collections
G_INF = 2 ** 31

class GraphError(Exception):
	pass

class GraphSearchError(GraphError):

	def __init__(self, reason):
		self.reason = reason

	def __str__(self):
		return str(reason)

class ShortestPathFasterAlgorithm(object):

	def __init__(self, number_of_vertices, adjacency_list, costs, start):
		self.max_v = number_of_vertices
		self.adj = adjacency_list
		self.costs = costs
		self.start = start
		self.dist = None
		self.visits = None

	def initialize(self):
		self.dist = collections.defaultdict(lambda : G_INF)
		self.dist[self.start] = 0
		self.visits = collections.defaultdict(int)

	def single_source_shortest_path(self):
		self.initialize()
		in_q = collections.defaultdict(bool)
		q = collections.deque()
		q.append(self.start)
		in_q[self.start] = True
		while q:
			u = q.popleft()
			in_q[u] = False
			self.visits[u] += 1
			if self.visits[u] >= self.max_v:
				if self.max_v == 1:
					return [0]
				raise GraphSearchError('A negative cycle was detected.')
			for v in self.adj[u]:
				new_length = self.dist[u] + self.costs[u, v]
				if new_length < self.dist[v]:
					self.dist[v] = new_length
					if not in_q[v]:
						q.append(v)
						in_q[v] = True
		return self.dist

def main():
	(max_v, max_e, start) = map(int, input().split())
	adjacency_list = collections.defaultdict(lambda : array.array('L'))
	costs = collections.defaultdict(lambda : G_INF)
	for _ in range(max_e):
		(s, t, d) = map(int, input().split())
		adjacency_list[s].append(t)
		costs[s, t] = d
	spfa = ShortestPathFasterAlgorithm(max_v, adjacency_list, costs, start)
	try:
		dist = spfa.single_source_shortest_path()
		for v in range(max_v):
			result = dist[v]
			if result < G_INF:
				print(result)
			else:
				print('INF')
	except GraphSearchError as gse:
		print('NEGATIVE CYCLE')
main()


import sys
INF = float('inf')

def Bellmanford(n, edges, r):
	d = [INF] * n
	d[r] = 0
	for i in range(n):
		for (u, v, c) in edges:
			if d[u] != INF and d[u] + c < d[v]:
				d[v] = d[u] + c
				if i == n - 1:
					return ['NEGATIVE CYCLE']
	d = [di if di < INF else 'INF' for di in d]
	return d
(V, E, R) = map(int, sys.stdin.readline().split())
Edges = [None] * E
for i in range(E):
	(si, ti, di) = map(int, sys.stdin.readline().split())
	Edges[i] = (si, ti, di)
ans = Bellmanford(V, Edges, R)
print(*ans, sep='\n')


import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

class BellmanFord:

	def __init__(self, V, edges, start):
		self.V = V
		self.edges = edges
		self.start = start

	def include_negative_cycle(self):
		d = [0] * self.V
		for i in range(self.V):
			for (s, e, c) in self.edges:
				if d[e] > d[s] + c:
					d[e] = d[s] + c
					if i == self.V - 1:
						return True
		return False

	def shortest_distance(self):
		d = [float('inf')] * self.V
		d[self.start] = 0
		self.prev = [None] * self.V
		loop_counter = 0
		while True:
			update = False
			for (s, e, c) in self.edges:
				if d[s] != float('inf') and d[e] > d[s] + c:
					d[e] = d[s] + c
					self.prev[e] = s
					update = True
			loop_counter += 1
			if loop_counter == self.V and update:
				d[self.start] = float('inf')
				break
			if not update:
				break
		return d

	def shortest_path(self, goal):
		path = []
		node = goal
		while node is not None:
			path.append(node)
			node = self.prev[node]
		return path[::-1]

def main():
	(V, _, r, *edge) = map(int, read().split())
	Edges = []
	for (a, b, w) in zip(*[iter(edge)] * 3):
		Edges.append((a, b, w))
	bf = BellmanFord(V, Edges, r)
	dist = bf.shortest_distance()
	if dist[r] == float('inf'):
		print('NEGATIVE CYCLE')
	else:
		for d in dist:
			print(d if d < float('inf') else 'INF')
main()


(num_v, num_e, source) = input().split()
edges = []
verticies = []
for i in range(int(num_e)):
	(v, u, w) = input().split()
	e = (int(v), int(u), int(w))
	edges.append(e)
for v in range(int(num_v)):
	v = str(v)
	verticies.append(v)
itn = int(num_v) - 1
g = edges
dist = [float('inf')] * (itn + 1)
dist[int(source)] = 0

def BF(g):
	for i in range(itn):
		for edge in edges:
			(v, u, w) = edge
			if dist[v] != float('inf'):
				if dist[v] + w < dist[u]:
					dist[u] = dist[v] + w
	ngc = 0
	for edge in edges:
		(v, u, w) = edge
		if dist[v] != float('inf'):
			if dist[v] + w < dist[u]:
				ngc = 1
	if ngc == 0:
		for i in range(itn + 1):
			if dist[i] == float('inf'):
				print('INF')
			else:
				print(dist[i])
	else:
		print('NEGATIVE CYCLE')
BF(g)


import sys
fin = sys.stdin.readline
MAX_NUM = float('inf')

def initialize_int(adj, s):
	N = len(adj)
	d = [MAX_NUM] * N
	d[s] = 0
	parent = [None] * N
	return (d, parent)

def relax(d, w, source_v, target_v, parent):
	new_cost = d[source_v] + w[source_v][target_v]
	if new_cost < d[target_v]:
		d[target_v] = new_cost
		parent[target_v] = source_v

def bellman_ford(adj, w, s):
	(d, parent) = initialize_int(adj, s)
	for _ in range(len(adj)):
		for vertex in range(len(adj)):
			for neighbor in adj[vertex]:
				relax(d, w, vertex, neighbor, parent)
	negative_cycle_edges = set()
	for vertex in range(len(adj)):
		for neighbor in adj[vertex]:
			if d[neighbor] > d[vertex] + w[vertex][neighbor]:
				negative_cycle_edges.add((vertex, neighbor))
	return (d, parent, negative_cycle_edges)
(V, E, r) = [int(elem) for elem in fin().split()]
adj = [[] for _ in range(V)]
w = [[None] * V for _ in range(V)]
for _ in range(E):
	(s, t, d) = [int(elem) for elem in fin().split()]
	adj[s].append(t)
	w[s][t] = d
(d, parent, negative_cycle_edges) = bellman_ford(adj, w, r)
if len(negative_cycle_edges) > 0:
	print('NEGATIVE CYCLE')
else:
	for i in range(V):
		print('INF') if d[i] == MAX_NUM else print(d[i])


(V, E, Start) = map(int, input().split())
INF = 10 ** 20
Edge = []
D = [INF] * V
for _ in range(E):
	Edge.append(list(map(int, input().split())))
D[Start] = 0
loop = 0
while True:
	update = False
	for i in range(E):
		fr = Edge[i][0]
		to = Edge[i][1]
		cost = Edge[i][2]
		if D[fr] != INF and D[to] > D[fr] + cost:
			D[to] = D[fr] + cost
			update = True
	if update == False:
		break
	loop += 1
	if loop > V:
		break
if loop > V:
	print('NEGATIVE CYCLE')
else:
	for d in D:
		if d == INF:
			print('INF')
		else:
			print(d)


d = []
(V, E, r) = list(map(int, input().split(' ')))
edges = [list(map(int, input().split(' '))) for i in range(E)]

def bellman_ford(s):
	global d
	d = [float('inf') for i in range(V)]
	d[s] = 0
	for i in range(V - 1):
		for (s, t, w) in edges:
			if d[t] > d[s] + w:
				d[t] = d[s] + w
	for (s, t, w) in edges:
		if d[s] + w < d[t]:
			return False
	return True
if bellman_ford(r):
	for w in d:
		if w == float('inf'):
			print('INF')
		else:
			print(w)
else:
	print('NEGATIVE CYCLE')


def bellman_ford(vertexes, edges, costs, start):
	d = [float('inf')] * vertexes
	d[start] = 0
	for i in range(vertexes):
		update = False
		for j in range(len(edges)):
			(frm, to) = edges[j]
			cost = costs[j]
			if d[to] > d[frm] + cost:
				d[to] = d[frm] + cost
				update = True
		if not update:
			break
		if i == n - 1:
			return -1
	return d
(n, m, s) = map(int, input().split())
edges = []
costs = [-float('inf')] * m
score = [-float('inf')] * (n + 1)
for i in range(m):
	(a, b, c) = map(int, input().split())
	edges.append([a, b])
	costs[i] = c
d = bellman_ford(n, edges, costs, s)
if d == -1:
	print('NEGATIVE CYCLE')
else:
	for i in range(n):
		print(d[i]) if d[i] != float('inf') else print('INF')


import sys
inf = int(1000000000000.0)

def shortestPath(graph, s):
	n = len(graph)
	dist = [inf for _ in range(n)]
	dist[s] = 0
	for i in range(n):
		for u in range(n):
			for (v, cost) in graph[u]:
				newDist = dist[u] + cost
				if dist[u] != inf and newDist < dist[v]:
					if i == n - 1:
						return None
					dist[v] = newDist
	return dist

def main():
	(v, e, s) = map(int, input().split())
	graph = [[] for _ in range(v)]
	for i in range(e):
		(a, b, cost) = map(int, input().split())
		graph[a].append((b, cost))
	dist = shortestPath(graph, s)
	if not dist:
		print('NEGATIVE CYCLE')
	else:
		for d in dist:
			if d >= inf:
				print('INF')
			else:
				print(d)
main()


from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def I():
	return int(sys.stdin.readline())

def LS():
	return [list(x) for x in sys.stdin.readline().split()]

def S():
	res = list(sys.stdin.readline())
	if res[-1] == '\n':
		return res[:-1]
	return res

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]
sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
	(n, m, r) = LI()
	v = [[] for i in range(n)]
	for i in range(m):
		(a, b, c) = LI()
		v[a].append((b, c))
	d = [float('inf')] * n
	d[r] = 0
	for i in range(n):
		update = 0
		for x in range(n):
			dx = d[x]
			for (y, c) in v[x]:
				nd = dx + c
				if nd < d[y]:
					d[y] = nd
					update = 1
		if not update:
			break
	else:
		print('NEGATIVE CYCLE')
		return
	for i in d:
		if i == float('inf'):
			print('INF')
		else:
			print(i)
	return
solve()


(V, E, r) = map(int, input().split())
inf = 2 ** 32
e = []
for i in range(E):
	(s, t, d) = map(int, input().split())
	e.append([s, t, d])
distance = [inf] * V
distance[r] = 0

def bellmanFord():
	for v in range(V):
		updated = False
		for (s, t, d) in e:
			if distance[s] != inf and distance[s] + d < distance[t]:
				distance[t] = distance[s] + d
				updated = True
		if v == V - 1 and updated:
			return False
	return True
b = bellmanFord()
if b:
	for v in range(V):
		print(distance[v] if distance[v] != inf else 'INF')
else:
	print('NEGATIVE CYCLE')


INF = 10 ** 30

def Belman_Ford(s, N):
	dist = [INF] * N
	dist[s] = 0
	cnt = 0
	neg = False
	while True:
		if cnt == N:
			break
		update = False
		for (f, t, c) in Edge:
			if dist[t] > dist[f] + c:
				if cnt < N - 1:
					if dist[f] != INF:
						dist[t] = min(dist[t], dist[f] + c)
						update = True
				else:
					neg = True
		if not update:
			break
		cnt += 1
	if neg:
		return -1
	else:
		return dist
(V, E, r) = map(int, input().split())
Edge = [tuple(map(int, input().split())) for i in range(E)]
res = Belman_Ford(r, V)
if type(res) is int:
	print('NEGATIVE CYCLE')
else:
	for i in range(V):
		print(res[i] if res[i] != INF else 'INF')


(v, e, r) = map(int, input().split())
d = [float('INF')] * v
edges = [[] for i in range(v)]
for i in range(e):
	(a, *s) = map(int, input().split())
	edges[a].append(s)
d[r] = 0
from collections import deque
for i in range(v + 2):
	f = False
	used = set()
	dq = deque([r])
	while dq:
		a = dq.popleft()
		for (to, c) in edges[a]:
			if d[to] > c + d[a]:
				f = True
				d[to] = c + d[a]
			if to not in used:
				dq.append(to)
				used.add(to)
	if i == v:
		print('NEGATIVE CYCLE')
		exit()
	if f:
		continue
	break
for i in d:
	print('INF' if i == float('INF') else i)


import sys
from math import isinf

def generate_adj_table(_v_info):
	for each in _v_info:
		(source, target, cost) = map(int, each)
		init_adj_table[source].setdefault(target, cost)
	return init_adj_table

def bellman_ford():
	distance[root] = 0
	for j in range(vertices - 1):
		for (current, current_info) in enumerate(adj_table):
			for (adj, cost) in current_info.items():
				if distance[current] + cost < distance[adj]:
					distance[adj] = distance[current] + cost
	for (current, current_info) in enumerate(adj_table):
		for (adj, cost) in current_info.items():
			if distance[current] + cost < distance[adj]:
				print('NEGATIVE CYCLE')
				return list()
	return distance
_input = sys.stdin.readlines()
(vertices, edges, root) = map(int, _input[0].split())
v_info = map(lambda x: x.split(), _input[1:])
distance = [float('inf')] * vertices
init_adj_table = tuple((dict() for _ in range(vertices)))
adj_table = generate_adj_table(v_info)
res = bellman_ford()
for ele in res:
	if isinf(ele):
		print('INF')
	else:
		print(ele)


def SPFA(G: list, source=0):
	from collections import deque
	V = len(G)
	d = [float('inf')] * V
	inQ = [False] * V
	cnt = [0] * V
	d[source] = 0
	cnt[source] = 1
	Q = deque([source])
	_sum = 0
	_len = 1
	while Q:
		f = Q.popleft()
		inQ[f] = False
		_sum -= d[f]
		_len -= 1
		for (t, c) in G[f]:
			dist = d[f] + c
			if dist < d[t]:
				d[t] = dist
				if not inQ[t]:
					inQ[t] = True
					cnt[t] += 1
					if dist * _len < _sum:
						Q.appendleft(t)
					else:
						Q.append(t)
					_sum += dist
					_len += 1
				if cnt[t] > V:
					return None
	return d

def main():
	(V, E, r, *L) = map(int, open(0).read().split())
	G = [[] for _ in range(V)]
	for (s, t, d) in zip(*[iter(L)] * 3):
		G[s].append((t, d))
	ret = SPFA(G, r)
	if ret == None:
		print('NEGATIVE CYCLE')
	else:
		for x in ret:
			print('INF' if x == float('inf') else x)
main()


from collections import deque
(V, E, r) = 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) = 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')
main()


import sys
input = sys.stdin.readline
from collections import deque

def main():
	(N, M, r) = map(int, input().split())
	d = dict()
	E = [[] for _ in range(N)]
	for _ in range(M):
		(a, b, c) = map(int, input().split())
		d[a, b] = c
		E[a].append(b)
	INF = 10 ** 14 * 2
	V = [INF] * N
	V[r] = 0
	for _ in range(N - 1):
		for e in d:
			(s, t) = e
			if V[s] + d[e] < V[t]:
				V[t] = V[s] + d[e]
	q = deque([r])
	W = [False] * N
	while q:
		v = q.pop()
		for w in E[v]:
			if W[w] == False:
				W[w] = True
				q.append(w)
	for e in d:
		(s, t) = e
		if V[s] + d[e] < V[t] and (W[s] == True or W[t] == True):
			print('NEGATIVE CYCLE')
			return
	for i in range(N):
		if V[i] >= 10 ** 14:
			print('INF')
			continue
		print(V[i])
main()


from collections import defaultdict
from collections import deque
from sys import stdin

def sp(G, R, V):
	d = {}
	INF = float('inf')
	for i in range(V):
		d[i] = INF
	d[R] = 0
	for i in range(1, V + 1):
		for ((u, v), c) in G.items():
			if d[v] > d[u] + c:
				d[v] = d[u] + c
				if i == V:
					return 0
	return d
(V, E, R) = [int(x) for x in stdin.readline().split()]
G = {}
for case in range(E):
	(s, t, w) = [int(x) for x in stdin.readline().split()]
	G[s, t] = w
d = sp(G, R, V)
if d == 0:
	print('NEGATIVE CYCLE')
else:
	for k in range(V):
		if d[k] == float('inf'):
			print('INF')
		else:
			print(d[k])


inf = float('inf')

class edge:

	def __init__(self, start, target, cost):
		self.start = start
		self.target = target
		self.cost = cost

def bellman_ford(s):
	d = [inf] * V
	d[s] = 0
	cnt = 0
	updateflag = True
	while True:
		updateflag = False
		for i in es:
			if d[i.start] != inf and d[i.target] > d[i.start] + i.cost:
				d[i.target] = d[i.start] + i.cost
				updateflag = True
		if cnt == V - 1:
			return False
		if not updateflag:
			break
		cnt += 1
	return d
(V, E, r) = map(int, input().split())
if E == 0:
	print(0)
else:
	es = [None] * E
	for i in range(E):
		(s, t, cost) = map(int, input().split())
		es[i] = edge(s, t, cost)
	ans = bellman_ford(r)
	if ans:
		for i in ans:
			if i == inf:
				print('INF')
			else:
				print(i)
	else:
		print('NEGATIVE CYCLE')


def main():
	(nvertices, nedges, s) = map(int, input().split())
	edges = []
	for i in range(nedges):
		(u, v, w) = 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:
		print(w if w < INF else 'INF')
main()


import queue

class Edge:

	def __init__(self, _to, _cost):
		self.to = _to
		self.cost = _cost

def bellman(n, graph, start):
	dist = [0 if i == start else float('inf') for i in range(n)]
	for i in range(n):
		for v in range(n):
			for e in graph[v]:
				if dist[v] == float('inf') or dist[e.to] <= dist[v] + e.cost:
					continue
				dist[e.to] = dist[v] + e.cost
				if i == n - 1:
					return None
	return dist

def main():
	(n, m, s) = map(int, input().split())
	graph = [[] for _ in range(n)]
	for _ in range(m):
		data = list(map(int, input().split()))
		graph[data[0]].append(Edge(data[1], data[2]))
	ans = bellman(n, graph, s)
	if ans is None:
		print('NEGATIVE CYCLE')
	else:
		for i in range(n):
			print(ans[i] if ans[i] != float('inf') else 'INF')
		return
main()


(nv, ne, r) = [int(i) for i in input().split()]
edges = [[int(i) for i in input().split()] for _ in range(ne)]
costs = [float('inf')] * nv
costs[r] = 0
for i in range(nv):
	is_updated = False
	for edge in edges:
		(f, t, c) = edge
		if costs[f] + c < costs[t]:
			costs[t] = costs[f] + c
			is_updated = True
if is_updated:
	print('NEGATIVE CYCLE')
else:
	for c in costs:
		print(c if c < float('inf') else 'INF')


import sys
stdin = sys.stdin
ns = lambda : stdin.readline().rstrip()
ni = lambda : int(ns())
na = lambda : list(map(int, stdin.readline().split()))
INF = int(1e+18)

class BellmanFord:
	N = -1
	edge = []

	def __init__(self, N):
		self.N = N

	def addEdge(self, a, b, cost):
		self.edge.append((a, b, cost))

	def addBiEdge(self, a, b, cost):
		self.addEdge(a, b, cost)
		self.addEdge(b, a, cost)

	def calc(self, start):
		dist = [INF] * self.N
		dist[start] = 0
		update = True
		cnt = 0
		while update:
			update = False
			cnt += 1
			if cnt > self.N:
				return -INF
			for (a, b, cost) in self.edge:
				ncost = dist[a] + cost
				if dist[a] == INF or ncost >= dist[b]:
					continue
				dist[b] = ncost
				update = True
		return dist

def main():
	(v, e, r) = na()
	BF = BellmanFord(v)
	for _ in range(e):
		BF.addEdge(*na())
	ans = BF.calc(r)
	if ans == -INF:
		print('NEGATIVE CYCLE')
	else:
		for i in range(v):
			print('INF' if ans[i] == INF else ans[i])
main()


from collections import defaultdict
import heapq
(vertice, edge, source) = 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) = 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 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


(V, E, root) = map(int, input().split())
visited = [False] * V
nodes = [[] for i in range(V)]
cost = [[] for i in range(V)]
for i in range(E):
	(s, t, d) = map(int, input().split())
	nodes[s].append(t)
	cost[s].append(d)
dist = [float('inf')] * V
dist[root] = 0
negative_cycle = False
for k in range(V):
	for i in range(V):
		for j in range(len(nodes[i])):
			if dist[nodes[i][j]] > dist[i] + cost[i][j]:
				dist[nodes[i][j]] = dist[i] + cost[i][j]
				if k == V - 1:
					dist[nodes[i][j]] = -float('inf')
					negative_cycle = True
if negative_cycle:
	print('NEGATIVE CYCLE')
else:
	for i in range(V):
		if dist[i] == float('inf'):
			print('INF')
		else:
			print(dist[i])


import sys
from math import isinf

def bellman_ford(start: int) -> bool:
	global dists, negatives
	global edges
	dists[start] = 0
	V = len(dists)
	for i in range(V):
		for (s, t, w) in edges:
			if isinf(dists[s]):
				continue
			if dists[t] > dists[s] + w:
				dists[t] = dists[s] + w
				if i == V - 1:
					negatives[t] = True
(V, E, start) = map(int, input().split())
edges = []
for _ in range(E):
	(s, t, d) = map(int, input().split())
	edges.append((s, t, d))
dists = [float('inf')] * V
negatives = [False] * V
bellman_ford(start)
if any((neg for neg in negatives)) == True:
	print('NEGATIVE CYCLE')
	exit()
for di in dists:
	if di == float('inf'):
		print('INF')
	else:
		print(di)


class BellmanFord:

	def __init__(self, V, E, start, INF=10 ** 9):
		self.V = V
		self.E = E
		self.bellman_ford(start, INF)

	def bellman_ford(self, start, INF):
		self.distance = [INF] * self.V
		self.prev = [-1] * self.V
		self.distance[start] = 0
		self.negativeCycle = False
		for i in range(V):
			update = False
			for v in range(V):
				for (to, cost) in self.E[v]:
					if self.distance[v] != INF and self.distance[v] + cost < self.distance[to]:
						self.distance[to] = self.distance[v] + cost
						self.prev[to] = v
						update = True
						if i == V - 1:
							self.negativeCycle = True
			if update == False:
				break

	def getPath(self, end):
		assert self.hasNegativeCycle() == False
		path = [end]
		while self.prev[end] != -1:
			end = self.prev[end]
		return path[::-1]

	def hasNegativeCycle(self):
		return self.negativeCycle
(V, E, r) = map(int, input().split())
INF = 10 ** 9
edge = [[] for _ in range(V)]
for _ in range(E):
	(s, t, d) = map(int, input().split())
	edge[s].append((t, d))
sp = BellmanFord(V, edge, r, INF)
if sp.hasNegativeCycle():
	print('NEGATIVE CYCLE')
else:
	print(*[dist if dist != INF else 'INF' for dist in sp.distance], sep='\n')


from collections import defaultdict
from collections import deque
from sys import stdin

def sp(G, R, V):
	d = {}
	INF = float('inf')
	for i in range(V):
		d[i] = INF
	d[R] = 0
	for i in range(1, V + 1):
		for (u, v) in G.keys():
			if d[v] > d[u] + G[u, v]:
				d[v] = d[u] + G[u, v]
				if i == V:
					return 'NEGATIVE CYCLE'
	return d
(V, E, R) = [int(x) for x in stdin.readline().split()]
G = defaultdict()
for case in range(E):
	(s, t, w) = [int(x) for x in stdin.readline().split()]
	G[s, t] = w
d = sp(G, R, V)
if d == 'NEGATIVE CYCLE':
	print('NEGATIVE CYCLE')
else:
	for k in range(V):
		if d[k] == float('inf'):
			print('INF')
		else:
			print(d[k])


from collections import defaultdict

def bellman_ford(V, E, s):
	INF = float('inf')
	N = len(V)
	dist = [INF] * N
	prev = [-1] * N
	dist[s] = 0
	for n_iterations in range(N):
		updated = False
		for v in V:
			d = dist[v]
			if d != INF:
				for (u, c) in E[v].items():
					temp = d + c
					if dist[u] > temp:
						updated = True
						dist[u] = temp
						prev[u] = v
		if not updated:
			break
	else:
		return None
	return dist
INF = float('inf')
(N, M, r) = map(int, input().split())
E = {i: defaultdict(int) for i in range(N)}
for _ in range(M):
	(a, b, c) = map(int, input().split())
	E[a][b] = c
V = list(range(N))
dist = bellman_ford(V, E, r)
if dist is None:
	print('NEGATIVE CYCLE')
else:
	for d in dist:
		if d == INF:
			print('INF')
		else:
			print(d)


(v, e, r) = map(int, input().split())
graph = [[] for _ in range(e)]
std = [list(map(int, input().split())) for _ in range(e)]

def bellman_ford(s):
	dist = [float('inf')] * v
	dist[s] = 0
	for u in range(v):
		for (s, t, d) in std:
			if dist[t] > dist[s] + d:
				dist[t] = dist[s] + d
				if u == v - 1:
					return -1
	return dist
dist = bellman_ford(r)
if dist == -1:
	print('NEGATIVE CYCLE')
else:
	for i in range(v):
		if dist[i] == float('inf'):
			print('INF')
			continue
		print(dist[i])


class exist_negative_cycle(Exception):
	pass

def bellman_ford(g, size, start=0):
	d = [float('inf')] * size
	d[start] = 0
	for _ in range(size):
		for u in g:
			for (length, v) in g[u]:
				if d[v] > d[u] + length:
					d[v] = d[u] + length
	for u in g:
		for (length, v) in g[u]:
			if d[v] > d[u] + length:
				raise exist_negative_cycle
	return d
from sys import stdin
readline = stdin.readline
import math
from collections import defaultdict
(vertex, edge, r) = map(int, readline().split())
g = defaultdict(list)
for i in range(edge):
	(s, t, length) = map(int, readline().split())
	g[s].append((length, t))
try:
	d = bellman_ford(g, vertex, r)
	for di in d:
		print('INF' if math.isinf(di) else di)
except exist_negative_cycle:
	print('NEGATIVE CYCLE')


import math

def main():
	(nvertices, nedges, s) = map(int, input().split())
	E = []
	for i in range(nedges):
		(u, v, w) = map(int, input().split())
		E.append((u, v, w))
	INF = float('inf')
	d = [INF] * nvertices
	d[s] = 0
	for i in range(nvertices - 1):
		for (u, v, w) in E:
			if d[u] + w < d[v]:
				d[v] = d[u] + w
	for i in range(nvertices - 1):
		for (u, v, w) in E:
			if d[v] > d[u] + w:
				print('NEGATIVE CYCLE')
				return
	for val in d:
		if math.isinf(val):
			print('INF')
		else:
			print(val)
main()


def func(r, V, edge):
	c = [float('inf')] * V
	update = True
	loop = 0
	c[r] = 0
	while update:
		update = False
		for s in range(V):
			for (t, d) in edge[s]:
				temp = c[s] + d
				if temp < c[t]:
					c[t] = temp
					update = True
		loop += 1
		if loop == V:
			break
	if loop == V and update:
		c[r] = float('inf')
	return c
(V, E, r) = map(int, input().split())
edge = [[] for _ in range(V)]
for _ in range(E):
	(s, t, d) = map(int, input().split())
	edge[s].append([t, d])
c = func(r, V, edge)
if c[r] == float('inf'):
	print('NEGATIVE CYCLE')
else:
	for temp in c:
		if temp == float('inf'):
			print('INF')
		else:
			print(temp)


def inpl():
	return tuple(map(int, input().split()))
INF = float('inf')
(V, E, r) = inpl()
edges = [inpl() for _ in range(E)]

def belman_ford(V, edges, r):
	D = [INF] * V
	D[r] = 0
	if V == 1:
		return ([0], [False])
	for _ in range(V):
		update = False
		for (s, t, d) in edges:
			if D[t] > D[s] + d:
				D[t] = D[s] + d
				update = True
		if not update:
			break
	else:
		NEGATIVE = [False] * V
		for (s, t, d) in edges:
			if D[t] > D[s] + d:
				D[t] = D[s] + d
				NEGATIVE[t] = True
				NEGATIVE[s] = True
		return (D, NEGATIVE)
	return (D, [False] * V)
(D, NEGATIVE) = belman_ford(V, edges, r)
if any(NEGATIVE):
	print('NEGATIVE CYCLE')
else:
	for d in D:
		print('INF') if d == INF else print(d)


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 sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect_left
from heapq import heappush, heappop

def input():
	return sys.stdin.readline().strip()

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST():
	return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

class BellmanFord:
	INF = int(1e+18)
	N = -1
	edge = []

	def __init__(self, N):
		self.N = N

	def add_edge(self, frm, to, cost):
		self.edge.append((frm, to, cost))

	def add_bi_edge(self, a, b, cost):
		self.add_edge(a, b, cost)
		self.add_edge(b, a, cost)

	def calcD(self, start):
		D = [self.INF] * self.N
		D[start] = 0
		(update, cnt) = (True, 0)
		while update:
			update = False
			cnt = cnt + 1
			if cnt > self.N:
				return None
			for (frm, to, cost) in self.edge:
				ncost = D[frm] + cost
				if D[frm] == self.INF or ncost >= D[to]:
					continue
				D[to] = ncost
				update = True
		return D
(V, E, r) = MAP()
std = [LIST() for _ in range(E)]
bf = BellmanFord(V)
for (s, t, d) in std:
	bf.add_edge(s, t, d)
ans = bf.calcD(r)
if not ans:
	print('NEGATIVE CYCLE')
else:
	for i in range(V):
		print('INF' if ans[i] == bf.INF else ans[i])


def Bellman_Ford(g, start):
	n = len(g)
	dist = [float('inf')] * n
	dist[start] = 0
	for i in [0] * n:
		updated = False
		for v in range(n):
			for (to, cost) in g[v]:
				if dist[to] <= dist[v] + cost:
					continue
				dist[to] = dist[v] + cost
				updated = True
		if not updated:
			break
	else:
		return (None, False)
	return (dist, True)
(v, e, r) = [int(i) for i in input().split()]
std = [[int(i) for i in input().split()] for _ in range(e)]
g = [[] for _ in range(v)]
for (s, t, d) in std:
	g[s].append((t, d))
(dist, tf) = Bellman_Ford(g, r)
if tf:
	for i in dist:
		print(i if i != float('inf') else 'INF')
else:
	print('NEGATIVE CYCLE')


import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10 ** 30

def make_adj_list(n, E):
	l = [[] for _ in range(n)]
	for i in range(E):
		(s, t, d) = map(int, input().strip().split())
		l[s].append([d, t])
	return l

def bellman_ford(n, s, l):
	dist = [INF] * n
	dist[s] = 0
	for i in range(n):
		for v in range(n):
			for k in range(len(l[v])):
				(cost, to) = l[v][k]
				if dist[v] != INF and dist[to] > dist[v] + cost:
					dist[to] = dist[v] + cost
					if i == n - 1:
						return (True, dist)
	return (False, dist)

def main():
	(v, e, r) = map(int, input().strip().split())
	l = make_adj_list(v, e)
	(is_negative_cycle, dist) = bellman_ford(v, r, l)
	if is_negative_cycle:
		print('NEGATIVE CYCLE')
		return
	for d in dist:
		if d == INF:
			print('INF')
		else:
			print(d)
main()


(n, e, r) = map(int, input().split())
inf = 1145141919810364364
es = []

def bf(st):
	d = [inf] * n
	d[st] = 0
	i = 0
	while True:
		update = False
		i += 1
		if i > n:
			return -1
		for (p, q, r) in es:
			if d[p] != inf and d[q] > d[p] + r:
				d[q] = d[p] + r
				update = True
		if update == False:
			break
	return d
for _ in range(e):
	(x, y, z) = map(int, input().split())
	es.append([x, y, z])
a = bf(r)
if bf(r) == -1:
	print('NEGATIVE CYCLE')
else:
	for i in range(n):
		if a[i] == inf:
			print('INF')
		else:
			print(a[i])


def main():
	(N, M, r) = map(int, input().split())
	edge = [list(map(int, input().split())) for _ in range(M)]
	dist = [float('inf')] * N
	dist[r] = 0
	for i in range(N):
		flag = False
		for (a, b, c) in edge:
			if dist[b] > dist[a] + c:
				dist[b] = dist[a] + c
				flag = True
		if flag is False:
			break
		elif i == N - 1:
			print('NEGATIVE CYCLE')
			exit()
	for i in range(N):
		if dist[i] == float('inf'):
			print('INF')
		else:
			print(dist[i])
main()


(V, E, r) = map(int, input().split())
nodes = [list(map(int, input().split())) for _ in range(E)]

def shortest_path(s):
	d = [float('inf') for i in range(V)]
	d[s] = 0
	for _ in range(V):
		update = False
		for i in range(E):
			e = nodes[i]
			if d[e[0]] != float('inf') and d[e[1]] > d[e[0]] + e[2]:
				d[e[1]] = d[e[0]] + e[2]
				update = True
	if update:
		return None
	else:
		return d
if not shortest_path(r):
	print('NEGATIVE CYCLE')
else:
	d = shortest_path(r)
	for i in range(V):
		if d[i] == float('inf'):
			print('INF')
		else:
			print(d[i])


def bellman_ford():
	edges = []
	inf = 1
	(n, m, s) = map(int, input().split())
	for i in range(m):
		(src, tgt, cost) = map(int, input().split())
		edges.append({'source': src, 'target': tgt, 'cost': cost})
		if cost > 0:
			inf += cost
	graph = [{'cost': inf, 'source': -1} for i in range(n)]
	graph[s]['cost'] = 0
	for i in range(n - 1):
		for edge in edges:
			src = edge['source']
			tgt = edge['target']
			if graph[src]['cost'] == inf:
				continue
			if graph[tgt]['cost'] > graph[src]['cost'] + edge['cost']:
				graph[tgt]['cost'] = graph[src]['cost'] + edge['cost']
				graph[tgt]['source'] = src
	for edge in edges:
		src = edge['source']
		tgt = edge['target']
		if graph[src]['cost'] == inf:
			continue
		if graph[tgt]['cost'] > graph[src]['cost'] + edge['cost']:
			print('NEGATIVE CYCLE')
			return
	for vertex in graph:
		print(vertex['cost']) if vertex['cost'] < inf else print('INF')
bellman_ford()


import sys
from typing import List, Tuple
(V, E, r) = map(lambda x: int(x), input().split())
edges: List[List[Tuple[int, int]]] = [[] for _ in range(V)]
dists = [sys.maxsize for _ in range(V)]
dists[r] = 0
for _ in range(E):
	(s, t, dist) = map(lambda x: int(x), input().split())
	edges[s].append((t, dist))
for _ in range(V):
	for vertex in range(V):
		if sys.maxsize != dists[vertex]:
			for (to, cost) in edges[vertex]:
				if cost + dists[vertex] < dists[to]:
					dists[to] = cost + dists[vertex]
for vertex in range(V):
	if sys.maxsize != dists[vertex]:
		for (to, cost) in edges[vertex]:
			if cost + dists[vertex] < dists[to]:
				print('NEGATIVE CYCLE')
				exit(0)
for dist in dists:
	if sys.maxsize == dist:
		print('INF')
	else:
		print(dist)


import collections

class BellmanFord:

	def __init__(self):
		self.edges = []

	def add(self, u, v, d, directed=False):
		if directed:
			self.edges.append([u, v, d])
		else:
			self.edges.append([u, v, d])
			self.edges.append([v, u, d])

	def BellmanFord_search(self, s):
		d = collections.defaultdict(lambda : float('inf'))
		d[s] = 0
		numEdges = len(self.edges)
		while True:
			update = False
			for i in range(numEdges):
				e = self.edges[i]
				if d[e[0]] != float('inf') and d[e[1]] > d[e[0]] + e[2]:
					d[e[1]] = d[e[0]] + e[2]
					update = True
			if not update:
				break
		return d

	def BellmanFord_negative_bool(self, numNodes, start, zero_indexed=False):
		d = collections.defaultdict(lambda : float('inf'))
		d[start] = 0
		numEdges = len(self.edges)
		for i in range(numNodes):
			for j in range(numEdges):
				e = self.edges[j]
				if d[e[1]] > d[e[0]] + e[2]:
					d[e[1]] = d[e[0]] + e[2]
					if i == numNodes - 1:
						return True
		return False
graph = BellmanFord()
(num_v, num_edges, start) = list(map(int, input().split()))
for i in range(num_edges):
	(u, v, w) = list(map(int, input().split()))
	graph.add(u, v, w, directed=True)
if graph.BellmanFord_negative_bool(num_v, start, zero_indexed=True):
	print('NEGATIVE CYCLE')
else:
	distances = graph.BellmanFord_search(start)
	for i in range(num_v):
		if distances[i] == float('inf'):
			print('INF')
		else:
			print(distances[i])


import sys
input = sys.stdin.readline

def bellman_ford(start: int, graph: list):
	INF = float('inf')
	n = len(graph)
	dist = [INF] * n
	dist[start] = 0
	if n == 1:
		return (False, [0])
	for _ in range(n - 1):
		update = False
		for (v, edges) in enumerate(graph):
			for (nxt_v, cost) in edges:
				if dist[nxt_v] > dist[v] + cost:
					dist[nxt_v] = dist[v] + cost
					update = True
		if not update:
			break
	else:
		return (True, dist)
	return (False, dist)
(v, e, r) = map(int, input().split())
info = [list(map(int, input().split())) for i in range(e)]
INF = 10 ** 18
graph = [[] for i in range(v)]
for (a, b, cost) in info:
	graph[a].append((b, cost))
(is_negative, dist) = bellman_ford(r, graph)
if is_negative:
	print('NEGATIVE CYCLE')
else:
	for num in dist:
		if num > 10 ** 12:
			print('INF')
		else:
			print(num)


import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def beruman(N, edges, start=0, negative_loop=False):
	find_negative = False
	dist = [INF] * N
	dist[start] = 0
	for i in range(N):
		update = False
		for (a, b, c) in edges:
			if dist[a] != INF and dist[b] > dist[a] + c:
				dist[b] = dist[a] + c
				update = True
		if not update:
			break
		if i == N - 1:
			find_negative = True
	if negative_loop:
		return (dist, find_negative)
	else:
		return dist

def main():
	(V, E, s) = map(int, input().split())
	edges = [tuple(map(int, input().split())) for _ in range(E)]
	(dist, flag) = beruman(V, edges, start=s, negative_loop=True)
	if flag:
		print('NEGATIVE CYCLE')
	else:
		print('\n'.join(map(lambda x: 'INF' if x == INF else str(x), dist)))
main()


INF = float('inf')

def bellman_ford(edges, num_v, sv):
	dist = [INF for i in range(num_v)]
	dist[sv] = 0
	for i in range(num_v):
		for edge in edges:
			(s, t, d) = (edge[0], edge[1], edge[2])
			if dist[s] != INF and dist[t] > dist[s] + d:
				dist[t] = dist[s] + d
				if i == num_v - 1:
					return -1
	return dist

def main():
	(N, M, r) = map(int, input().split())
	edges = []
	for _ in range(M):
		(s, t, d) = map(int, input().split())
		edges.append([s, t, d])
	dist = bellman_ford(edges, N, r)
	if dist == -1:
		print('NEGATIVE CYCLE')
	else:
		for i in range(N):
			ans = dist[i]
			if ans == INF:
				ans = 'INF'
			print(ans)
main()


def bellmanford(G, s):
	n = len(G)
	inf = float('inf')
	dist = [inf] * n
	dist[s] = 0
	for i in range(2 * n):
		for v in range(n):
			for (w, c) in G[v]:
				if dist[w] > dist[v] + c:
					dist[w] = dist[v] + c
					if i >= n - 1:
						return -1
	return dist
import sys
input = sys.stdin.readline

def main():
	inf = float('inf')
	(V, E, r) = map(int, input().split())
	graph = [[] for _ in range(V)]
	for _ in range(E):
		(s, t, d) = map(int, input().split())
		graph[s].append((t, d))
	dist = bellmanford(graph, r)
	if dist == -1:
		print('NEGATIVE CYCLE')
	else:
		for d in dist:
			if d == inf:
				print('INF')
			else:
				print(d)
main()


import math
inf = math.inf
negative_cycle_flag = False

def INITSS(G, s):
	G.V_d[s] = 0

def RELAX(u, v, w, V_d, V_pi):
	if V_d[v] > V_d[u] + w[u][v]:
		V_d[v] = V_d[u] + w[u][v]
		V_pi[v] = u

def BELLMANFORD(G, s, w):
	global negative_cycle_flag
	INITSS(G, s)
	for i in range(1, len(G.V_d)):
		for (u, v) in G.E:
			RELAX(u, v, w, G.V_d, G.V_pi)
	for (u, v) in G.E:
		if G.V_d[u] + w[u][v] < G.V_d[v]:
			negative_cycle_flag = True
			break

class Graph:

	def __init__(self, v_num, e_num, E):
		self.V_d = [inf for _ in range(v_num)]
		self.V_pi = [None for _ in range(v_num)]
		self.E = E
(v_num, e_num, s) = map(int, input().split())
E = []
w = [[inf for _ in range(v_num)] for _ in range(v_num)]
for _ in range(e_num):
	(u, v, weight) = map(int, input().split())
	w[u][v] = weight
	E.append((u, v))
G = Graph(v_num, e_num, E)
BELLMANFORD(G, s, w)
if negative_cycle_flag == True:
	print('NEGATIVE CYCLE')
else:
	for k in range(v_num):
		if G.V_d[k] == inf:
			print('INF')
		else:
			print(G.V_d[k])


(V, E, r) = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(E)]
dp = [float('INF')] * V
dp[r] = 0
cnt = 0
while True:
	cnt += 1
	if cnt > V:
		print('NEGATIVE CYCLE')
		exit()
	flag = False
	for (s, t, d) in edges:
		if dp[t] > dp[s] + d:
			dp[t] = dp[s] + d
			flag = True
	if not flag:
		break
for c in dp:
	if c == float('INF'):
		print('INF')
	else:
		print(c)


(v, e, r) = map(int, input().split())
a = []
for i in range(e):
	A = list(map(int, input().split()))
	a.append(A)
costs = [None] * v
costs[r] = 0
count = 0
while True:
	count += 1
	update = False
	for (s, t, d) in a:
		if costs[s] is None:
			continue
		cost = costs[s] + d
		if costs[t] is None or costs[t] > cost:
			costs[t] = cost
			update = True
	if not update:
		for cost in costs:
			print('INF' if cost is None else cost)
		break
	if count == v:
		print('NEGATIVE CYCLE')
		break


import os
import sys

def main():
	(V, E, R) = read_ints()
	D = [tuple(read_ints()) for _ in range(E)]
	print(*solve(V, E, R, D), sep='\n')

def solve(V, E, R, D):
	INF = 10001 * 1000
	dists = [INF] * V
	dists[R] = 0
	for _ in range(V - 1):
		for (s, t, d) in D:
			if dists[s] != INF and dists[t] > dists[s] + d:
				dists[t] = dists[s] + d
	for (s, t, d) in D:
		if dists[s] != INF and dists[s] + d < dists[t]:
			return ['NEGATIVE CYCLE']
	return ['INF' if d == INF else d for d in dists]
DEBUG = 'DEBUG' in os.environ

def inp():
	return sys.stdin.readline().rstrip()

def read_int():
	return int(inp())

def read_ints():
	return [int(e) for e in inp().split()]

def dprint(*value, sep=' ', end='\n'):
	if DEBUG:
		print(*value, sep=sep, end=end)
main()


class BellmanFord:
	INF = int(1e+18)
	N = -1
	edge = []

	def __init__(self, N):
		self.N = N

	def add_edge(self, frm, to, cost):
		self.edge.append((frm, to, cost))

	def add_bi_edge(self, a, b, cost):
		self.add_edge(a, b, cost)
		self.add_edge(b, a, cost)

	def calcD(self, start):
		D = [self.INF] * self.N
		D[start] = 0
		(update, cnt) = (True, 0)
		while update:
			update = False
			cnt = cnt + 1
			if cnt > self.N:
				return 'NegativeCycle'
			for (frm, to, cost) in self.edge:
				ncost = D[frm] + cost
				if D[frm] == self.INF or ncost >= D[to]:
					continue
				D[to] = ncost
				update = True
		return D
(V, E, S) = list(map(int, input().split()))
bf = BellmanFord(V)
for i in range(E):
	(frm, to, cost) = list(map(int, input().split()))
	bf.add_edge(frm, to, cost)
ans = bf.calcD(S)
if ans == 'NegativeCycle':
	print('NEGATIVE CYCLE')
else:
	for i in range(V):
		print('INF' if ans[i] == bf.INF else ans[i])


(n, m, r) = map(int, input().split())
(a, b, c) = ([0] * m, [0] * m, [0] * m)
INF = 10 ** 18
for i in range(m):
	(a[i], b[i], c[i]) = map(int, input().split())
d = [INF] * n
d[r] = 0
for _ in range(n - 1):
	for i in range(m):
		if d[a[i]] == INF:
			continue
		d[b[i]] = min(d[b[i]], d[a[i]] + c[i])
for _ in range(n):
	for i in range(m):
		if d[a[i]] == INF:
			continue
		if d[b[i]] > d[a[i]] + c[i]:
			print('NEGATIVE CYCLE')
			exit()
for i in d:
	print([i, 'INF'][i == INF])


import sys
iim = lambda : map(int, sys.stdin.readline().rstrip().split())
from collections import defaultdict

def resolve():
	it = map(int, sys.stdin.read().split())
	(V, E, r) = (next(it), next(it), next(it))
	inf = float('inf')
	dp = [inf] * V
	dp[r] = 0
	dx = defaultdict(list)
	for (si, ti, di) in zip(it, it, it):
		dx[si].append((ti, di))
	(sx, tx) = ({r}, set())
	for i in range(V + 1):
		if not sx:
			break
		for si in sx:
			for (ti, di) in dx[si]:
				d1 = dp[ti]
				d2 = dp[si] + di
				if d1 > d2:
					dp[ti] = d2
					tx.add(ti)
		(sx, tx) = (tx, set())
	if sx:
		print('NEGATIVE CYCLE')
		return
	ans = []
	print(*['INF' if x == inf else x for x in dp], sep='\n')
resolve()


from sys import stdin

def sp(G, R, V):
	d = {}
	INF = float('inf')
	for i in range(V):
		d[i] = INF
	d[R] = 0
	for i in range(1, V + 1):
		for (u, v) in G.keys():
			if d[v] > d[u] + G[u, v]:
				d[v] = d[u] + G[u, v]
				if i == V:
					print('NEGATIVE CYCLE')
					quit()
	return d
(V, E, R) = [int(x) for x in stdin.readline().split()]
G = {}
for case in range(E):
	(s, t, w) = [int(x) for x in stdin.readline().split()]
	G[s, t] = w
d = sp(G, R, V)
for k in range(V):
	if d[k] == float('inf'):
		print('INF')
	else:
		print(d[k])


from collections import defaultdict
from collections import deque
from sys import stdin

def sp(G, R, V):
	d = {}
	INF = float('inf')
	for i in range(V):
		d[i] = INF
	d[R] = 0
	for i in range(1, V + 1):
		for (u, v) in G.keys():
			if d[v] > d[u] + G[u, v]:
				d[v] = d[u] + G[u, v]
				if i == V:
					return 0
	return d
(V, E, R) = [int(x) for x in stdin.readline().split()]
G = {}
for case in range(E):
	(s, t, w) = [int(x) for x in stdin.readline().split()]
	G[s, t] = w
d = sp(G, R, V)
if d == 0:
	print('NEGATIVE CYCLE')
else:
	for k in range(V):
		if d[k] == float('inf'):
			print('INF')
		else:
			print(d[k])


INF = 10 ** 20
(v_num, e_num, r) = map(int, input().split())
dist_lst = [INF for _ in range(v_num)]
edges_lst = [[] for _ in range(e_num)]
negative_cycle_flag = False
for _ in range(e_num):
	(s, t, dist) = map(int, input().split())
	edges_lst[s].append((dist, t))
dist_lst[r] = 0
if e_num != 0:
	for _ in range(v_num):
		for v in range(v_num):
			if dist_lst[v] != INF:
				for (dist, to) in edges_lst[v]:
					if dist_lst[v] + dist < dist_lst[to]:
						dist_lst[to] = dist_lst[v] + dist
	for v in range(v_num):
		if dist_lst[v] != INF:
			for (dist, to) in edges_lst[v]:
				if dist_lst[v] + dist < dist_lst[to]:
					negative_cycle_flag = True
					break
			if negative_cycle_flag:
				break
if negative_cycle_flag:
	print('NEGATIVE CYCLE')
else:
	for dist in dist_lst:
		if dist == INF:
			print('INF')
		else:
			print(dist)


def solve(V, E, r, edges):
	cost = [float('inf')] * V
	cost[r] = 0
	for _ in range(V - 1):
		for edge in edges:
			s = edge[0]
			t = edge[1]
			d = edge[2]
			if cost[t] > cost[s] + d:
				cost[t] = cost[s] + d
	for edge in edges:
		s = edge[0]
		t = edge[1]
		d = edge[2]
		if cost[t] > cost[s] + d:
			return []
	return cost
(V, E, r) = map(int, input().split())
edges = []
for _ in range(E):
	(s, t, d) = map(int, input().split())
	edges.append(tuple((s, t, d)))
ans = solve(V, E, r, edges)
if len(ans) == 0:
	print('NEGATIVE CYCLE')
else:
	for i in range(len(ans)):
		if ans[i] == float('inf'):
			print('INF')
		else:
			print(ans[i])


def inpl():
	return tuple(map(int, input().split()))
INF = float('inf')
(V, E, r) = inpl()
edges = [inpl() for _ in range(E)]

def belman_ford(V, edges, r):
	D = [INF] * V
	D[r] = 0
	if V == 1:
		return (False, [0])
	for _ in range(V - 1):
		update = False
		for (s, t, d) in edges:
			if D[t] > D[s] + d:
				D[t] = D[s] + d
				update = True
		if not update:
			break
	else:
		return (True, D)
	return (False, D)
(NEGATIVE, D) = belman_ford(V, edges, r)
if NEGATIVE:
	print('NEGATIVE CYCLE')
else:
	for d in D:
		print('INF') if d == INF else print(d)


import heapq
(n, m, r) = list(map(int, input().split()))
V = [i for i in range(n)]
E = [{} for _ in range(n)]
for _ in range(m):
	(ef, et, ed) = list(map(int, input().split()))
	E[ef][et] = ed
INF = int(1e+18)
dist = {i: INF for i in range(n)}
pred = {i: None for i in range(n)}
dist[r] = 0
update = True
count = 0
while update:
	update = False
	count += 1
	if count > n:
		print('NEGATIVE CYCLE')
		exit()
	for u in range(n):
		for v in E[u]:
			d = E[u][v]
			if dist[u] == INF or dist[u] + d >= dist[v]:
				continue
			else:
				dist[v] = dist[u] + d
				pred[v] = u
				update = True
for v in range(n):
	if dist[v] == INF:
		print('INF')
	else:
		print(dist[v])


(v, e, r) = map(int, input().split())
std = [list(map(int, input().split())) for _ in range(e)]

def BellmanFord(edges, num_v, source):
	inf = float('inf')
	dist = [inf for i in range(num_v)]
	dist[source] = 0
	for i in range(num_v):
		for edge in edges:
			if edge[0] != inf and dist[edge[1]] > dist[edge[0]] + edge[2]:
				dist[edge[1]] = dist[edge[0]] + edge[2]
				if i == num_v - 1:
					return (False, [])
	return (True, dist)
(flag, distance) = BellmanFord(std, v, r)
if flag:
	for i in range(v):
		if distance[i] != float('inf'):
			print(distance[i])
		else:
			print('INF')
else:
	print('NEGATIVE CYCLE')


from collections import defaultdict
INF = 999999999999999999999
NEGATIVE_CYCLE = -1

def bellman_ford(G, n, r):
	d = {}
	for i in range(n):
		d[i] = INF
	d[r] = 0
	for i in range(n - 1):
		d = relax(G, d)
	for u in G:
		for v in G[u]:
			if d[u] == INF and d[v] == INF:
				continue
			if d[u] + G[u][v] < d[v]:
				return NEGATIVE_CYCLE
	return d

def relax(G, d):
	for u in G:
		if d[u] == INF:
			continue
		for v in G[u]:
			if d[u] + G[u][v] < d[v]:
				d[v] = d[u] + G[u][v]
	return d
G = {}
(n, m, r) = [int(v) for v in input().strip().split(' ')]
for i in range(n):
	G[i] = {}
for _ in range(m):
	(s, t, c) = [int(v) for v in input().strip().split(' ')]
	G[s][t] = c
d = bellman_ford(G, n, r)
if d == NEGATIVE_CYCLE:
	print('NEGATIVE CYCLE')
else:
	for i in range(n):
		if d[i] == INF:
			print('INF')
		else:
			print(d[i])


import sys
(v, e, r) = map(int, input().split())
E = [[] for _ in range(v)]
inf = 10 ** 12
for _ in range(e):
	(s, t, d) = map(int, input().split())
	E[s].append([t, d])
D = [inf for _ in range(v)]
D[r] = 0
for _ in range(v):
	for ve in range(v):
		for ed in E[ve]:
			D[ed[0]] = min(D[ed[0]], D[ve] + ed[1])
for i in range(v):
	if E[i]:
		for ed in E[i]:
			if D[i] + ed[1] < D[ed[0]] and D[ed[0]] < inf // 10:
				print('NEGATIVE CYCLE')
				sys.exit()
for i in range(v):
	if D[i] < inf // 100:
		print(D[i])
	else:
		print('INF')


from collections import deque

def find_negative_loop():
	INF = float('inf')
	(V, E, r) = map(int, input().split())
	dist = [INF] * V
	dist[r] = 0
	es = deque()
	for i in range(E):
		(s, t, d) = map(int, input().split())
		es.append((s, t, d))
	for i in range(V):
		for e in es:
			(f, t, c) = e
			if dist[f] != INF and dist[t] > dist[f] + c:
				dist[t] = dist[f] + c
				if i == V - 1:
					return (True, dist)
	return (False, dist)

def main():
	INF = float('inf')
	(is_negative, dist) = find_negative_loop()
	if is_negative:
		print('NEGATIVE CYCLE')
	else:
		for d in dist:
			if d == INF:
				print('INF')
			else:
				print(d)
main()


from collections import deque
(N, M, r) = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
	(s, t, d) = 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')


(N, E, r) = map(int, input().split())
G = []
for i in range(E):
	(s, t, d) = map(int, input().split())
	G.append([d, s, t])

def bellman_ford(G, s):
	INF = 10 ** 9
	d = [INF] * N
	d[s] = 0
	j = 0
	while True:
		update = False
		for i in range(E):
			(cost, fro, to) = G[i]
			if d[fro] != INF and d[to] > d[fro] + cost:
				d[to] = d[fro] + cost
				update = True
				if j == N - 1:
					return (True, 0)
		j += 1
		if not update:
			break
	return (False, d)
(bool, d) = bellman_ford(G, r)
if bool:
	print('NEGATIVE CYCLE')
else:
	for i in range(N):
		if d[i] == 10 ** 9:
			print('INF')
		else:
			print(d[i])


(V, E, r) = map(int, input().split())
INF = float('inf')
edges = []
for _ in range(E):
	(s, d, c) = map(int, input().split())
	edges.append([s, d, c])
dist = [INF] * V
dist[r] = 0
for _ in range(V - 1):
	for (s, d, c) in edges:
		if dist[d] > dist[s] + c:
			dist[d] = dist[s] + c
for (s, d, c) in edges:
	if dist[d] > dist[s] + c:
		print('NEGATIVE CYCLE')
		exit()
for d in dist:
	print(d if d != INF else 'INF')


import sys
from collections import namedtuple, deque
INF = sys.maxsize
Edge = namedtuple('Edge', 's t d')
(V, E, r) = map(int, input().split())
edges = []
for _ in range(E):
	(s, t, d) = map(int, input().split())
	edges.append(Edge(s, t, d))

def solve():
	costs = [INF] * V
	costs[r] = 0
	for i in range(V):
		for edge in edges:
			if costs[edge.s] != INF and costs[edge.t] > costs[edge.s] + edge.d:
				if i == V - 1:
					print('NEGATIVE CYCLE')
					return
				costs[edge.t] = costs[edge.s] + edge.d
	for x in costs:
		print(x if x != INF else 'INF')
solve()


(nv, ne, r) = map(int, input().split())
edges = set((tuple(map(int, input().split())) for _ in range(ne)))
costs = [None] * nv
costs[r] = 0
for _ in range(nv - 1):
	for (s, t, d) in edges:
		if costs[s] is None:
			continue
		cost = costs[s] + d
		if costs[t] is None or costs[t] > cost:
			costs[t] = cost
for (s, t, d) in edges:
	if costs[s] is None:
		continue
	if costs[s] + d < costs[t]:
		print('NEGATIVE CYCLE')
		break
else:
	for cost in costs:
		print('INF' if cost is None else cost)


import math

def main():
	(nvertices, nedges, s) = map(int, input().split())
	edges = []
	for i in range(nedges):
		(u, v, w) = 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()


(V, E, r) = map(int, input().split())
es = []
for i in range(E):
	(s, t, d) = map(int, input().split())
	es.append((s, t, d))
inf = 10 ** 18
d = [inf for i in range(V)]
d[r] = 0
cnt = 0
while True:
	update = False
	for i in range(E):
		e = es[i]
		if d[e[0]] != inf and d[e[1]] > d[e[0]] + e[2]:
			d[e[1]] = d[e[0]] + e[2]
			update = True
	if update == False:
		break
	cnt += 1
	if cnt >= V:
		break
if cnt >= V:
	print('NEGATIVE CYCLE')
else:
	for i in range(V):
		if d[i] == inf:
			print('INF')
		else:
			print(d[i])


(N, M, S) = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(M):
	(a, b, l) = map(int, input().split())
	G[a].append([b, l])
INF = 10 ** 10

def bellman_ford(G, N, S):
	res = [INF for _ in range(N)]
	res[S] = 0
	for _ in range(N - 1):
		for i in range(N):
			if res[i] == INF:
				continue
			for (sa, sb) in G[i]:
				res[sa] = min(res[sa], res[i] + sb)
	for i in range(N):
		if res[i] == INF:
			continue
		for (sa, sb) in G[i]:
			if res[sa] > res[i] + sb:
				return False
	return res
res = bellman_ford(G, N, S)
if res == False:
	print('NEGATIVE CYCLE')
else:
	for i in range(N):
		if res[i] == INF:
			print('INF')
		else:
			print(res[i])


(V, E, r) = 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) = 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')
main()


import sys
readline = sys.stdin.readline
(V, E, r) = map(int, readline().split())
inf = 10 ** 10
edges = [[] for _ in [None] * V]
for _ in [None] * E:
	(s, t, d) = map(int, readline().split())
	edges[s].append((t, d))
vertices = [inf] * V
vertices[r] = 0
for i in range(V):
	flag = 0
	for v in range(V):
		cost = vertices[v]
		if cost == inf:
			continue
		for (dist, _cost) in edges[v]:
			newcost = cost + _cost
			if vertices[dist] > newcost:
				vertices[dist] = newcost
				flag = 1
	if flag == 0:
		for v in vertices:
			print(v if v != inf else 'INF')
		break
else:
	print('NEGATIVE CYCLE')


import math

def main():
	(nvertices, nedges, s) = map(int, input().split())
	E = []
	for i in range(nedges):
		(u, v, w) = 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()


(V, E, r) = map(int, input().split())
g = []
for i in range(E):
	(s, t, d) = map(int, input().split())
	g.append([s, t, d])
inf = 1001001001
dd = [inf] * V
dd[r] = 0
for i in range(V - 1):
	update = 0
	for (s, t, d) in g:
		if dd[t] > dd[s] + d and dd[s] != inf:
			dd[t] = dd[s] + d
			update += 1
	if update == 0:
		break
update = False
for (s, t, d) in g:
	if dd[t] > dd[s] + d and dd[s] != inf:
		update = True
		break
if update:
	print('NEGATIVE CYCLE')
else:
	for i in dd:
		if i == inf:
			print('INF')
		else:
			print(i)


import sys, collections
(N, E, r) = tuple(map(int, sys.stdin.readline().split()))
sdw = tuple((tuple(map(int, sys.stdin.readline().rstrip().split())) for _ in range(E)))
INF = float('inf')
ALL = set(range(N))
distances = collections.defaultdict(lambda : INF)
distances[r] = 0
for _ in range(N):
	modified = False
	for (src, dst, weight) in sdw:
		if distances[dst] > distances[src] + weight:
			distances[dst] = distances[src] + weight
			modified = True
	if modified == False:
		for i in range(N):
			if distances[i] == INF:
				print('INF')
			else:
				print(distances[i])
		exit()
print('NEGATIVE CYCLE')


from heapq import heappop, heappush, heapify

class Graph:

	def __init__(self, n, edge, directed=False):
		self.n = n
		self.graph = [[] for _ in range(n)]
		for e in edge:
			self.graph[e[0]].append((e[1], e[2]))
			if not directed:
				self.graph[e[1]].append((e[0], e[2]))

	def bellman_ford(self, s, INF=10 ** 18):
		dist = [INF for _ in range(self.n)]
		dist[s] = 0
		update = True
		for i in range(self.n):
			update = False
			for (node, g) in enumerate(self.graph):
				for (adj, adjcost) in g:
					if dist[node] != INF and dist[node] + adjcost < dist[adj]:
						dist[adj] = dist[node] + adjcost
						update = True
			if not update:
				return dist
		return False
INF = 10 ** 18
import sys
input = sys.stdin.readline
(V, E, r) = map(int, input().split())
edge = [tuple(map(int, input().split())) for _ in range(E)]
g = Graph(V, edge, True)
D = g.bellman_ford(r, INF)
if D:
	for i in range(V):
		if D[i] == INF:
			D[i] = 'INF'
	print('\n'.join(map(str, D)))
else:
	print('NEGATIVE CYCLE')


(nv, ne, r) = map(int, input().split(' '))
dist = [float('inf')] * nv
dist[r] = 0
edges = []
for i in range(ne):
	(s, t, w) = map(int, input().split(' '))
	edges.append((s, t, w))
for i in range(nv - 1):
	for (s, t, w) in edges:
		if dist[t] > dist[s] + w:
			dist[t] = dist[s] + w
for (s, t, w) in edges:
	if dist[t] > dist[s] + w:
		print('NEGATIVE CYCLE')
		exit()
[print(d) if d < float('inf') else print('INF') for d in dist]


import sys
sys.setrecursionlimit(10 ** 9)

def input():
	return sys.stdin.readline().strip()

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST():
	return list(map(int, input().split()))
INF = float('inf')

def bellman_ford(N: int, edges: list, src: int) -> list:
	res = [INF] * N
	res[src] = 0
	for i in range(N - 1):
		for (src, dest, cost) in edges:
			if res[dest] > res[src] + cost:
				res[dest] = res[src] + cost
	for (src, dest, cost) in edges:
		if res[dest] > res[src] + cost:
			return []
	return res
(N, M, r) = MAP()
edges = [None] * M
for i in range(M):
	(s, t, d) = MAP()
	edges[i] = (s, t, d)
ans = bellman_ford(N, edges, r)
if not len(ans):
	print('NEGATIVE CYCLE')
	exit()
for i in range(N):
	if ans[i] == INF:
		ans[i] = 'INF'
for i in range(N):
	print(ans[i])


import string
import sys
from itertools import chain, dropwhile, takewhile
INF = float('inf')

def read(*shape, f=int, it=chain.from_iterable(sys.stdin), whitespaces=set(string.whitespace)):

	def read_word():
		w = lambda c: c in whitespaces
		nw = lambda c: c not in whitespaces
		return f(''.join(takewhile(nw, dropwhile(w, it))))
	if not shape:
		return read_word()
	elif len(shape) == 1:
		return [read_word() for _ in range(shape[0])]
	elif len(shape) == 2:
		return [[read_word() for _ in range(shape[1])] for _ in range(shape[0])]

def readi(*shape):
	return read(*shape)

def readi1(*shape):
	return [i - 1 for i in readi(*shape)]

def readf(*shape):
	return read(*shape, f=float)

def reads(*shape):
	return read(*shape, f=str)

def arr(*shape, fill_value=0):
	if len(shape) == 1:
		return [fill_value] * shape[0]
	elif len(shape) == 2:
		return [[fill_value] * shape[1] for _ in range(shape[0])]

def dbg(**kwargs):
	print(', '.join(('{} = {}'.format(k, repr(v)) for (k, v) in kwargs.items())), file=sys.stderr)

def main():
	(V, E, r) = readi(3)
	edges = readi(E, 3)
	dist = arr(V, fill_value=INF)
	dist[r] = 0
	for i in range(V):
		for (a, b, c) in edges:
			new_d = dist[a] + c
			if new_d < dist[b]:
				dist[b] = new_d
				if i == V - 1:
					print('NEGATIVE CYCLE')
					return
	for i in range(V):
		print('INF' if dist[i] == INF else dist[i])
main()


(n, m, r) = map(int, input().split())
E = [tuple(map(int, input().split())) for j in range(m)]
inf = 10 ** 20
D = [inf for i in range(n)]
D[r] = 0
flag = True
cnt = 0
while flag:
	flag = False
	cnt += 1
	if cnt > n:
		print('NEGATIVE CYCLE')
		exit()
	for (s, t, d) in E:
		if D[s] != inf and D[t] > D[s] + d:
			D[t] = D[s] + d
			flag = True
for i in range(n):
	if D[i] == inf:
		print('INF')
	else:
		print(D[i])


import sys
from math import isinf

def generate_adj_table(_v_info):
	for each in _v_info:
		(source, target, cost) = map(int, each)
		init_adj_table[source][target] = cost
	return init_adj_table

def bellman_ford():
	distance[root] = 0
	for j in range(vertices - 1):
		for (current, current_info) in enumerate(adj_table):
			for (adj, cost) in current_info.items():
				if distance[current] + cost < distance[adj]:
					distance[adj] = distance[current] + cost
	for (current, current_info) in enumerate(adj_table):
		for (adj, cost) in current_info.items():
			if distance[current] + cost < distance[adj]:
				print('NEGATIVE CYCLE')
				return list()
	return distance
_input = sys.stdin.readlines()
(vertices, edges, root) = map(int, _input[0].split())
v_info = map(lambda x: x.split(), _input[1:])
distance = [float('inf')] * vertices
init_adj_table = tuple((dict() for _ in range(vertices)))
adj_table = generate_adj_table(v_info)
res = bellman_ford()
for ele in res:
	if isinf(ele):
		print('INF')
	else:
		print(ele)


(v, e, r) = map(int, input().split())
edges = []
for _ in range(e):
	(s, t, d) = map(int, input().split())
	edges.append((s, t, d))

def shortest_path(v, s, edges, inf):
	d = [inf] * v
	d[s] = 0
	cnt = 0
	while True:
		cnt += 1
		update = False
		for (frm, to, cost) in edges:
			if d[frm] != inf and d[to] > d[frm] + cost:
				d[to] = d[frm] + cost
				update = True
		if cnt == v and update:
			return False
		elif not update:
			break
	return d
inf = 10 ** 9
d = shortest_path(v, r, edges, inf)
if d == False:
	print('NEGATIVE CYCLE')
else:
	for i in range(v):
		if d[i] == inf:
			print('INF')
		else:
			print(d[i])


import sys
from math import isinf

class Edge(object):
	__slots__ = ('source', 'target', 'cost')

	def __init__(self):
		self.cost = float('inf')
		(self.source, self.target) = (None, None)

def generate_edge_table(_v_info):
	for (index, each) in enumerate(_v_info):
		edge = init_edge_table[index]
		(source, target, cost) = map(int, each)
		edge.source = source
		edge.target = target
		edge.cost = cost
	return init_edge_table

def bellman_ford():
	distance[root] = 0
	for j in range(vertices - 1):
		for edge in edge_table:
			(source, target, cost) = (edge.source, edge.target, edge.cost)
			if distance[source] + cost < distance[target]:
				distance[target] = distance[source] + cost
	for edge in edge_table:
		(source, target, cost) = (edge.source, edge.target, edge.cost)
		if distance[source] + cost < distance[target]:
			print('NEGATIVE CYCLE')
			return list()
	return distance
_input = sys.stdin.readlines()
(vertices, edges, root) = map(int, _input[0].split())
v_info = map(lambda x: x.split(), _input[1:])
distance = [float('inf')] * vertices
init_edge_table = tuple((Edge() for _ in range(edges)))
edge_table = generate_edge_table(v_info)
res = bellman_ford()
for ele in res:
	if isinf(ele):
		print('INF')
	else:
		print(ele)


from typing import List, Optional, Tuple

def bellman_ford(source: int, vertices_count: int, edges: List[Tuple]) -> Optional[List[float]]:
	inf = float('inf')
	dist = [inf] * (vertices_count + 1)
	dist[source] = 0
	for i in range(vertices_count):
		for (from_, to, weight) in edges:
			if dist[from_] + weight < dist[to]:
				dist[to] = dist[from_] + weight
				if i == vertices_count - 1:
					return None
	return dist

def main():
	(V, E, R, *edges) = map(int, open(0).read().split())
	dist = bellman_ford(R, V, list(zip(*[iter(edges)] * 3)))
	inf = float('inf')
	if dist:
		print('\n'.join(map(str, (i if i != inf else 'INF' for i in dist[:-1]))))
	else:
		print('NEGATIVE CYCLE')
main()