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):
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')

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


if __name__ == '__main__':
    main()

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


if __name__ == '__main__':
    main()

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


if __name__ == '__main__':
    main()

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

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

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

Solution (Python):


def bellman_ford(s):
    '''
    始点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)

Solution (Python):

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):
        """ 2頂点と、辺のコストを追加する """
        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):
        """ 2頂点と、辺のコストを追加する (無向グラフ) """
        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

if __name__ == "__main__":
    main()

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

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

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

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

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

Solution (Python):
"""


Verified:
    https://onlinejudge.u-aizu.ac.jp/problems/GRL_1_B
"""
from typing import List, Optional, Tuple


def bellman_ford(
    source: int, vertices_count: int, edges: List[Tuple]
) -> Optional[List[float]]:
    """Bellman-Ford algorithm: O(NM)
    Compute the distance of the shortest path from V_source to each vertex.
    Relax edges in N-1 times of loops and detect negative cycles in the last loop.

    Args:
        source: V_source
        edges: Edges info
        vertices_count: Number of vertices
    Returns:
        Return None if the graph has negative cycles.
        If not, return a list of distance from V_source.
    """
    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")


if __name__ == "__main__":
    main()

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


if __name__ == '__main__':
    main()

Solution (Python):


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



if __name__ == "__main__":
    resolve()

Solution (Python):
class Edge():
    def __init__(self, src, to, weight):
        self.src = src
        self.to = to
        self.weight = weight

class NegativeWeightDirectedGraph():
    def __init__(self, V):
        self.V = V
        self.Edges = []
        self.INF = 10**10

    def append(self, src, to, weight):
        self.Edges.append(Edge(src, to, weight))

    def bellmanFord(self, s):
        D = [self.INF] * self.V
        D[s] = 0
        for _ in range(self.V-1):
            for e in self.Edges:
                if D[e.src] != self.INF:
                    w = D[e.src] + e.weight
                    D[e.to] = min(D[e.to], w)
        
        for e in self.Edges:
            if D[e.src] == self.INF:
                continue
            if D[e.src] + e.weight < D[e.to]:
                return None
        return D


V,E,r = map(int, raw_input().split())
G = NegativeWeightDirectedGraph(V)
for i in range(E):
    s,t,d = map(int, raw_input().split())
    G.append(s,t,d)

ans = G.bellmanFord(r)
if ans == None:
    print "NEGATIVE CYCLE"
else:
    for d in ans:
        if d == G.INF:
            print "INF"
        else:
            print d

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

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

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

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

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


if __name__ == '__main__':
    main()

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

Solution (Python):

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)

Solution (Python):

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

Solution (Python):

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


class BellmanFord:
    """
    shortest_distance(goal): startノードからgoalノードまでの最短距離
    shortest_path(goal): startノードからgoalノードまでの最短経路
    include_negative_cycle(): 負閉路の存在確認
    """
    def __init__(self, V, edges, start):
        """
        V : 頂点数
        edges: (辺の始点,辺の終点,辺のコスト)を要素とする辺のリスト
        start: 始点のノード番号
        """
        self.V = V
        self.edges = edges
        self.start = start

    def include_negative_cycle(self):
        """
        負閉路の存在確認
        Returns: True or False
        """
        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):
        """ 
        始点から頂点goalまでの最短距離をを返す 
        """
        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):
        """
        始点から頂点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")


if __name__ == "__main__":
    main()

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

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

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