Problem:
Single Source Shortest Path (Negative Edges) Input An edge-weighted graph G ( V , E ) and the source r . | V | | E | r  s 0  t 0  d 0  s 1  t 1  d 1 : 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.  s i and t i represent source and target vertices of i -th edge (directed) and d i 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   c 0  c 1 : 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 ".  Constraints   1 ≤ |V| ≤ 1000  0 ≤ |E| ≤ 2000  -10000 ≤ d i ≤ 10000  There are no parallel edges  There are no self-loops   Sample Input 1  4 5 0
0 1 2
0 2 3
1 2 -5
1 3 1
2 3 2  Sample Output 1  0
2
-3
-1   Sample Input 2  4 6 0
0 1 2
0 2 3
1 2 -5
1 3 1
2 3 2
3 1 0  Sample Output 2  NEGATIVE CYCLE   Sample Input 3  4 5 1
0 1 2
0 2 3
1 2 -5
1 3 1
2 3 2  Sample Output 3  INF
0
-5
-3

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

if __name__ == '__main__':
    main()

Solution (Python):
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")

Solution (Python):
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
        else:
            if i == N - 1:
                print('NEGATIVE CYCLE')
                exit()

    for i in range(N):
        if dist[i] == float('inf'):
            print('INF')
        else:
            print(dist[i])


if __name__ == '__main__':
    main()

Solution (Python):

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

Solution (Python):
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")

Solution (Python):




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

Solution (Python):

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


if __name__ == "__main__":
    solve()

Solution (Python):
import sys
input = sys.stdin.readline


def bellman_ford(start: int, graph: list):
    """bellman-ford法: 始点startから各頂点への最短距離を求める(負辺OK)
    計算量: O(|E||V|)
    """
    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)

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

Solution (Python):
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])

Solution (Python):
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])

Solution (Python):
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')

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

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

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







































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

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

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

if __name__ == '__main__':
    main()

Solution (Python):


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)

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

Solution (Python):


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)


if __name__ == '__main__':
    main()

Solution (Python):
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 ve in range(v):
    for ed in E[ve]:
        D[ed[0]] = min(D[ed[0]], D[ve] + ed[1])
    print(*D)
"""
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")

Solution (Python):
import sys

stdin = sys.stdin

ns = lambda : stdin.readline().rstrip()
ni = lambda : int(ns())
na = lambda : list(map(int, stdin.readline().split()))

INF = int(1e18)

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

Solution (Python):
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)
			
if __name__=="__main__":main()

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

if __name__ == '__main__':
    main()

Solution (Python):
import sys
from typing import List, Tuple


if __name__ == "__main__":
    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)

Solution (Python):
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")

Solution (Python):
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])
    
    
    
    
    
    
    
    
    
    
    
    
    
        
if __name__ == '__main__':
    main()

Solution (Python):

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


if __name__ == "__main__":
    main()

Solution (Python):


"""
Bellman_Ford
単一始点最短経路を求める
g: グラフの隣接リスト
start: 始点
返り値: dist, is_OK (負回路なしならTrue)
"""
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        
    

"""

AOJ: GRL_1_B http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_B


"""

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

Solution (Python):
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])

Solution (Python):
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])