human
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
Using python3 can you solve the prior task?

=====
Write me a Python code to print the cost of the shortest path from the source r to each vertex 0, 1,?
assistant
#Here is Python code to print the cost of the shortest path from the source r to each vertex 0, 1, .

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
#  ...