output_description: 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".
input_description: 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.
attempt: # Edige Weighted Digraph
  
  
  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))
  
  
  if __name__ == "__main__":
      run()
  
problem_description: Single Source Shortest Path (Negative Edges)
samples: [{"input": "4 5 0\n    0 1 2\n    0 2 3\n    1 2 -5\n    1 3 1\n    2 3 2", "output": "0\n    2\n    -3\n    -1"}, {"input": "4 6 0\n    0 1 2\n    0 2 3\n    1 2 -5\n    1 3 1\n    2 3 2\n    3 1 0", "output": "NEGATIVE CYCLE"}, {"input": "4 5 1\n    0 1 2\n    0 2 3\n    1 2 -5\n    1 3 1\n    2 3 2", "output": "INF\n    0\n    -5\n    -3"}]