Problem: 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

Solution (in PYTHON3):

Solution:
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(1e18)
    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

# 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

V, E, r = MAP()

std = [LIST() for _ in range(E)]
# edges = [[] for _ in range(V)]

# for s, t, d in std:
#     edges[s].append((t, d))

# dist = SPFA(V, edges, r)

# if not dist:
#     print("NEGATIVE CYCLE")
# else:
#     for i in range(V):
#         print(dist[i] if dist[i] < INF else "INF")

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])