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



"""
input:
4 5 1
0 1 2
0 2 3
1 2 -5
1 3 1
2 3 2

output:
INF
0
-5
-3

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

import sys
from math import isinf


def generate_adj_table(_v_info):
    for each in _v_info:
        source, target, cost = map(int, each)
        init_adj_table[source][target] = cost
    return init_adj_table


def bellman_ford():
    distance[root] = 0

    for j in range(vertices - 1):
        for current, current_info in enumerate(adj_table):
            for adj, cost in current_info.items():
                if distance[current] + cost < distance[adj]:
                    distance[adj] = distance[current] + cost

    for current, current_info in enumerate(adj_table):
        for adj, cost in current_info.items():
            if distance[current] + cost < distance[adj]:
                print('NEGATIVE CYCLE')
                return list()

    return distance


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices, edges, root = map(int, _input[0].split())
    v_info = map(lambda x: x.split(), _input[1:])

    distance = [float('inf')] * vertices
    init_adj_table = tuple(dict() for _ in range(vertices))

    adj_table = generate_adj_table(v_info)

    res = bellman_ford()
    for ele in res:
        if isinf(ele):
            print('INF')
        else:
            print(ele)

Solution (Python):



"""
input:
4 5 1
0 1 2
0 2 3
1 2 -5
1 3 1
2 3 2

output:
INF
0
-5
-3

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

import sys
from math import isinf


def generate_adj_table(_v_info):
    for each in _v_info:
        source, target, cost = map(int, each)
        init_adj_table[source][target] = cost
    return init_adj_table


def bellman_ford():
    distance[root] = 0

    for j in range(vertices - 1):
        for current, current_info in enumerate(adj_table):
            for adj, cost in current_info.items():
                if distance[current] + cost < distance[adj]:
                    distance[adj] = distance[current] + cost

    for current, current_info in enumerate(adj_table):
        for adj, cost in current_info.items():
            if distance[current] + cost < distance[adj]:
                print('NEGATIVE CYCLE')
                return list()

    return distance


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices, edges, root = map(int, _input[0].split())
    v_info = map(lambda x: x.split(), _input[1:])

    distance = [float('inf')] * vertices
    init_adj_table = tuple(dict() for _ in range(vertices))

    adj_table = generate_adj_table(v_info)

    res = bellman_ford()
    for ele in res:
        if isinf(ele):
            print('INF')
        else:
            print(ele)

Solution (Python):



"""
input:
4 5 1
0 1 2
0 2 3
1 2 -5
1 3 1
2 3 2

output:
INF
0
-5
-3

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

import sys
from math import isinf


def generate_adj_table(_v_info):
    for each in _v_info:
        source, target, cost = map(int, each)
        init_adj_table[source][target] = cost
    return init_adj_table


def bellman_ford():
    distance[root] = 0

    for j in range(vertices - 1):
        for current, current_info in enumerate(adj_table):
            for adj, cost in current_info.items():
                if distance[current] + cost < distance[adj]:
                    distance[adj] = distance[current] + cost

    for current, current_info in enumerate(adj_table):
        for adj, cost in current_info.items():
            if distance[current] + cost < distance[adj]:
                print('NEGATIVE CYCLE')
                return list()

    return distance


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices, edges, root = map(int, _input[0].split())
    v_info = map(lambda x: x.split(), _input[1:])

    distance = [float('inf')] * vertices
    init_adj_table = tuple(dict() for _ in range(vertices))

    adj_table = generate_adj_table(v_info)

    res = bellman_ford()
    for ele in res:
        if isinf(ele):
            print('INF')
        else:
            print(ele)

Solution (Python):



"""
input:
4 5 1
0 1 2
0 2 3
1 2 -5
1 3 1
2 3 2

output:
INF
0
-5
-3

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

import sys
from math import isinf


class Edge(object):
    __slots__ = ('source', 'target', 'cost')

    def __init__(self):
        self.cost = float('inf')
        self.source, self.target = None, None


def generate_edge_table(_v_info):
    for index, each in enumerate(_v_info):
        edge = init_edge_table[index]
        source, target, cost = map(int, each)
        edge.source = source
        edge.target = target
        edge.cost = cost
    return init_edge_table


def bellman_ford():
    distance[root] = 0

    for j in range(vertices - 1):
        for edge in edge_table:
            source, target, cost = edge.source, edge.target, edge.cost
            if distance[source] + cost < distance[target]:
                distance[target] = distance[source] + cost

    for edge in edge_table:
        source, target, cost = edge.source, edge.target, edge.cost
        if distance[source] + cost < distance[target]:
            print('NEGATIVE CYCLE')
            return list()

    return distance


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices, edges, root = map(int, _input[0].split())
    v_info = map(lambda x: x.split(), _input[1:])
    

    distance = [float('inf')] * vertices
    init_edge_table = tuple(Edge() for _ in range(edges))

    edge_table = generate_edge_table(v_info)

    res = bellman_ford()
    if res:
        print('\n'.join(('INF' if isinf(ele) else str(ele) for ele in res)))

Solution (Python):



"""
input:
4 5 1
0 1 2
0 2 3
1 2 -5
1 3 1
2 3 2

output:
INF
0
-5
-3

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

import sys
from math import isinf


def generate_adj_table(_v_info):
    for each in _v_info:
        source, target, cost = map(int, each)
        init_adj_table[source][target] = cost
    return init_adj_table


def bellman_ford():
    distance[root] = 0

    for j in range(vertices - 1):
        for current, current_info in enumerate(adj_table):
            for adj, cost in current_info.items():
                if distance[current] + cost < distance[adj]:
                    distance[adj] = distance[current] + cost

    for current, current_info in enumerate(adj_table):
        for adj, cost in current_info.items():
            if distance[current] + cost < distance[adj]:
                print('NEGATIVE CYCLE')
                return list()

    return distance


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices, edges, root = map(int, _input[0].split())
    v_info = map(lambda x: x.split(), _input[1:])

    distance = [float('inf')] * vertices
    init_adj_table = tuple(dict() for _ in range(vertices))

    adj_table = generate_adj_table(v_info)

    res = bellman_ford()
    for ele in res:
        if isinf(ele):
            print('INF')
        else:
            print(ele)

Solution (Python):



"""
input:
4 5 1
0 1 2
0 2 3
1 2 -5
1 3 1
2 3 2

output:
INF
0
-5
-3

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

import sys
from math import isinf


def generate_adj_table(_v_info):
    for each in _v_info:
        source, target, cost = map(int, each)
        init_adj_table[source].setdefault(target, cost)
    return init_adj_table


def bellman_ford():
    distance[root] = 0

    for j in range(vertices - 1):
        for current, current_info in enumerate(adj_table):
            for adj, cost in current_info.items():
                if distance[current] + cost < distance[adj]:
                    distance[adj] = distance[current] + cost

    for current, current_info in enumerate(adj_table):
        for adj, cost in current_info.items():
            if distance[current] + cost < distance[adj]:
                print('NEGATIVE CYCLE')
                return list()

    return distance


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices, edges, root = map(int, _input[0].split())
    v_info = map(lambda x: x.split(), _input[1:])

    distance = [float('inf')] * vertices
    init_adj_table = tuple(dict() for _ in range(vertices))

    adj_table = generate_adj_table(v_info)

    res = bellman_ford()
    for ele in res:
        if isinf(ele):
            print('INF')
        else:
            print(ele)

Solution (Python):
nv, ne, r = map(int, input().split(' '))
dist = [float('inf')] * nv
dist[r] = 0
edges = []
for i in range(ne):
    s, t, w = map(int, input().split(' '))
    edges.append((s, t, w))

for i in range(nv - 1):
    for s, t, w in edges:
        if dist[t] > dist[s] + w:
            dist[t] = dist[s] + w

for s, t, w in edges:
    if dist[t] > dist[s] + w:
        print("NEGATIVE CYCLE")
        exit()

[print(d) if d < float('inf') else print("INF") for d in dist]

Solution (Python):
from collections import defaultdict
from collections import deque
from sys import stdin

def sp(G,R,V):
    d = {}
    INF = float('inf')
    for i in range(V):
        d[i] = INF
    d[R] = 0
    for i in range(1,V+1):
        for (u,v) in G.keys():
            if d[v] > d[u] + G[u,v]:
                d[v] = d[u] + G[u,v]
                if i == V:
                    return 'NEGATIVE CYCLE'
    return d


V, E, R = [int(x) for x in stdin.readline().split()]
G = defaultdict()
for case in range(E):
    s, t, w = [int(x) for x in stdin.readline().split()]
    G[(s,t)] = w
d = sp(G, R, V)
if d == 'NEGATIVE CYCLE':
    print('NEGATIVE CYCLE')
else:
    for k in range(V):
        if d[k] == float('inf'):
            print("INF")
        else:
            print(d[k])

Solution (Python):
from collections import defaultdict
from collections import deque
from sys import stdin

def sp(G,R,V):
    d = {}
    INF = float('inf')
    for i in range(V):
        d[i] = INF
    d[R] = 0
    for i in range(1, V+1):
        for (u, v) in G.keys():
            if d[v] > d[u] + G[u, v]:
                d[v] = d[u] + G[u, v]
                if i == V:
                    return 0
    return d


V, E, R = [int(x) for x in stdin.readline().split()]
G = {}
for case in range(E):
    s, t, w = [int(x) for x in stdin.readline().split()]
    G[(s, t)] = w
d = sp(G, R, V)
if d == 0:
    print('NEGATIVE CYCLE')
else:
    for k in range(V):
        if d[k] == float('inf'):
            print("INF")
        else:
            print(d[k])

Solution (Python):
from sys import stdin
from collections import deque


V, E, R = [int(x) for x in stdin.readline().split()]
d = {}
tick = False
INF = float('inf')
for i in range(V):
    d[i] = INF
d[R] = 0
weight = {}
st = deque([])
for i in range(1, V+1):

    for j in range(E):
        if i == 1:
            s, t, w = [int(x) for x in stdin.readline().split()]
            weight[(s, t)] = w
            st.append((s, t))
        (s, t) = st.popleft()
        if d[t] > d[s] + weight[(s, t)]:
            d[t] = d[s] + weight[(s, t)]
            if i == V:
                print('NEGATIVE CYCLE')
                tick = True
                break
        st.append((s, t))


if not tick:
    for k in range(V):
        if d[k] == float('inf'):
            print("INF")
        else:
            print(d[k])

Solution (Python):
from sys import stdin

def sp(G,R,V):
    d = {}
    INF = float('inf')
    for i in range(V):
        d[i] = INF
    d[R] = 0
    for i in range(1, V+1):
        for (u, v) in G.keys():
            if d[v] > d[u] + G[u, v]:
                d[v] = d[u] + G[u, v]
                if i == V:
                    print('NEGATIVE CYCLE')
                    quit()
    return d


V, E, R = [int(x) for x in stdin.readline().split()]
G = {}
for case in range(E):
    s, t, w = [int(x) for x in stdin.readline().split()]
    G[(s, t)] = w
d = sp(G, R, V)
for k in range(V):
    if d[k] == float('inf'):
        print("INF")
    else:
        print(d[k])

Solution (Python):
from sys import stdin
from collections import deque

V, E, R = [int(x) for x in stdin.readline().split()]
d = {}
tick = False
INF = float('inf')
for i in range(V):
    d[i] = INF
d[R] = 0
weight = {}
st = []
for i in range(1, V+1):
    for j in range(E):
        if i == 1:
            s, t, w = [int(x) for x in stdin.readline().split()]
            weight[(s, t)] = w
            st.append((s, t))
        (s, t) = st[j]
        if d[t] > d[s] + weight[(s, t)]:
            d[t] = d[s] + weight[(s, t)]
            if i == V:
                print('NEGATIVE CYCLE')
                quit()

for k in range(V):
    if d[k] == float('inf'):
        print("INF")
    else:
        print(d[k])

Solution (Python):
from collections import defaultdict
import heapq

vertice,edge,source = map(int,input().split(" "))
link = defaultdict(dict)
weight = defaultdict(dict)
cost = [float("inf") for n in range(vertice)]
cost[source] = 0
for e in range(edge):
    i,j,w = map(int,input().split(" "))
    link[i] = link.get(i,set()) | {j}
    weight[i].update({j:w})

vertice_cnt = 0
while True:
    if vertice_cnt >= vertice:
        print("NEGATIVE CYCLE")
        break
    update = False
    for k,val in link.items():
        for v in val:
            if cost[v] > cost[k] + weight[k][v]:
                cost[v] = cost[k] + weight[k][v]
                update = True
    if not(update):
        for c in cost:
            print(c if c != float("inf") else "INF")
        break
    vertice_cnt += 1

Solution (Python):
from collections import defaultdict
from collections import deque
from sys import stdin
 
def sp(G,R,V):
    d = {}
    INF = float('inf')
    for i in range(V):
        d[i] = INF
    d[R] = 0
    for i in range(1, V+1):
        for ((u, v), c) in G.items():
            if d[v] > d[u] + c:
                d[v] = d[u] + c
                if i == V:
                    return 0
    return d
 
 
V, E, R = [int(x) for x in stdin.readline().split()]
G = {}
for case in range(E):
    s, t, w = [int(x) for x in stdin.readline().split()]
    G[(s, t)] = w
d = sp(G, R, V)
if d == 0:
    print('NEGATIVE CYCLE')
else:
    for k in range(V):
        if d[k] == float('inf'):
            print("INF")
        else:
            print(d[k])

Solution (Python):
import sys

inf = 1<<60

def solve():
    N, M, r = map(int, sys.stdin.readline().split())
    edges = [None] * M

    for i in range(M):
        si, ti, di = map(int, sys.stdin.readline().split())
        edges[i] = (si, ti, di)

    ans = BellmanFord(N, M, edges, r)

    print(*ans, sep='\n')

def BellmanFord(N, M, edges, r):
    d = [inf] * N
    d[r] = 0

    for i in range(N):
        flag = False

        for (u, v, c) in edges:
            if d[u] != inf and d[u] + c < d[v]:
                d[v] = d[u] + c
                flag = True

        if flag and i == N - 1:
            return ['NEGATIVE CYCLE']

    d = [di if di < inf else 'INF' for di in d]

    return d

if __name__ == '__main__':
    solve()

Solution (Python):
inf = float("inf")

class edge():
    def __init__(self, start, target, cost):
        self.start = start
        self.target = target
        self.cost = cost

def bellman_ford(s):
    d = [inf] * V
    d[s] = 0
    cnt = 0
    updateflag = True
    while True:
        updateflag = False
        for i in es:
            if d[i.start] != inf and d[i.target] > d[i.start] + i.cost:
                d[i.target] = d[i.start] + i.cost
                updateflag = True
        if cnt == V-1: return False
        if not updateflag: break
        cnt += 1
    return d

V,E,r = map(int, input().split())
if E == 0: print(0)
else:
 es = [None] * E
 for i in range(E):
     s,t,cost = map(int, input().split())
     es[i] = edge(s, t, cost)
 ans = bellman_ford(r)
 if ans:
     for i in ans:
         if i == inf: print("INF")
         else: print(i)
 else:
    print("NEGATIVE CYCLE")

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

V, E, r = map(int, readline().split())
inf = 10**10
edges = [[] for _ in [None]*V]

for _ in [None]*E:
    s, t, d = map(int, readline().split())
    edges[s].append((t, d))

vertices = [inf] * V
vertices[r] = 0

for i in range(V):
    flag = 0
    for v in range(V):
        cost = vertices[v]
        if cost == inf:
            continue
        for dist, _cost in edges[v]:
            newcost = cost + _cost
            if vertices[dist] > newcost:
                vertices[dist] = newcost
                flag = 1
    if flag == 0:
        for v in vertices:
            print(v if v != inf else "INF")
        break
else:
    print("NEGATIVE CYCLE")

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

V, E, r = map(int, readline().split())
inf = 10**10
edges = [[] for _ in [None]*V]

for _ in [None]*E:
    s, t, d = map(int, readline().split())
    edges[s].append((t, d))


def bellman_ford(n, edges, start):
    vertices = [inf] * n
    vertices[start] = 0
    reached = {start}

    for i in range(n):
        flag = 0
        for v in reached.copy():
            cost = vertices[v]
            for dist, _cost in edges[v]:
                newcost = cost + _cost
                if vertices[dist] > newcost:
                    vertices[dist] = newcost
                    reached.add(dist)
                    flag = 1
        if flag == 0:
            return vertices
    else:
        return None

result = bellman_ford(V, edges, r)
if result:
    print("\n".join([str(n) if n!=inf else "INF" for n in result]))
else:
    print("NEGATIVE CYCLE")

Solution (Python):
def main():
    nvertices, nedges, s = map(int, input().split())
    E = []
    for i in range(nedges):
        u, v, w = map(int, input().split())
        E.append((u, v, w))

    INF = 1000000000
    d = [INF] * nvertices
    d[s] = 0
    for i in range(nvertices - 1):
        for u, v, w in E:
            if d[u] == INF:
                continue
            if d[u] + w < d[v]:
                d[v] = d[u] + w

    for i in range(nvertices - 1):
        for u, v, w in E:
            if d[v] == INF:
                continue
            if d[v] > d[u] + w:
                print("NEGATIVE CYCLE")
                return

    for val in d:
        if val >= INF:
            print("INF")
        else:
            print(val)


main()

Solution (Python):
import math


def main():
    nvertices, nedges, s = map(int, input().split())
    E = []
    for i in range(nedges):
        u, v, w = map(int, input().split())
        E.append((u, v, w))

    INF = float('inf')
    d = [INF] * nvertices
    d[s] = 0
    for i in range(nvertices - 1):
        for u, v, w in E:
            if d[u] + w < d[v]:
                d[v] = d[u] + w

    for i in range(nvertices - 1):
        for u, v, w in E:
            if d[v] > d[u] + w:
                print("NEGATIVE CYCLE")
                return

    for val in d:
        if math.isinf(val):
            print("INF")
        else:
            print(val)


main()

Solution (Python):
import math


def main():
    nvertices, nedges, s = map(int, input().split())
    E = []
    for i in range(nedges):
        u, v, w = map(int, input().split())
        E.append((u, v, w))
    INF = float('inf')
    weights = [INF] * nvertices
    weights[s] = 0
    for i in range(nvertices - 1):
        for u, v, w in E:
            if weights[v] > weights[u] + w:
                weights[v] = weights[u] + w
    for u, v, w in E:
        if weights[v] > weights[u] + w:
            print("NEGATIVE CYCLE")
            return

    for w in weights:
        if math.isinf(w):
            print("INF")
        else:
            print(w)


main()

Solution (Python):
import math


def main():
    nvertices, nedges, s = map(int, input().split())
    edges = []
    for i in range(nedges):
        u, v, w = map(int, input().split())
        edges.append((u, v, w))

    INF = float('inf')
    weights = [INF] * nvertices
    weights[s] = 0
    for i in range(nvertices - 1):
        for u, v, w in edges:
            if weights[v] > weights[u] + w:
                weights[v] = weights[u] + w

    for u, v, w in edges:
        if weights[v] > weights[u] + w:
            print("NEGATIVE CYCLE")
            return

    for w in weights:
        if math.isinf(w):
            print("INF")
        else:
            print(w)


main()

Solution (Python):
from collections import defaultdict

INF = 999999999999999999999
NEGATIVE_CYCLE = -1

def bellman_ford(G, n, r):
  d = {}
  for i in range(n):
    d[i] = INF
  d[r] = 0
  for i in range(n-1):
    d = relax(G, d)
  for u in G:
    for v in G[u]:
      if d[u] == INF and d[v] == INF:
        continue
      if d[u] + G[u][v] < d[v]:
        return NEGATIVE_CYCLE
  return d

def relax(G, d):
  for u in G:
    if d[u] == INF:
      continue
    for v in G[u]:
      if d[u] + G[u][v] < d[v]:
        d[v] = d[u] + G[u][v]
  return d


G = {}

n, m, r = [int(v) for v in input().strip().split(' ')]
for i in range(n):
  G[i] = {}
for _ in range(m):
  s, t, c = [int(v) for v in input().strip().split(' ')]
  G[s][t] = c

d = bellman_ford(G, n, r)

if d == NEGATIVE_CYCLE:
  print("NEGATIVE CYCLE")
else:
  for i in range(n):
    if d[i] == INF:
      print("INF")
    else:
      print(d[i])

Solution (Python):
def main():
    nvertices, nedges, s = map(int, input().split())
    edges = []
    for i in range(nedges):
        u, v, w = map(int, input().split())
        edges.append((u, v, w))

    INF = float('inf')
    weights = [INF] * nvertices
    weights[s] = 0
    for i in range(nvertices - 1):
        for u, v, w in edges:
            if weights[v] > weights[u] + w:
                weights[v] = weights[u] + w

    for u, v, w in edges:
        if weights[v] > weights[u] + w:
            print("NEGATIVE CYCLE")
            return

    for w in weights:
        print(w if w < INF else 'INF')


main()

Solution (Python):
import sys

INF = float('inf')

def Bellmanford(n, edges, r):
    d = [INF] * n
    d[r] = 0
    
    for i in range(n):
        flag = False
        
        for (u, v, c) in edges:
            if d[u] != INF and d[u] + c < d[v]:
                d[v] = d[u] + c
                flag = True
                
        if flag and i == n-1:
            return ['NEGATIVE CYCLE']
        
    d = [di if di < INF else 'INF' for di in d]
    return d

V, E, R = map(int, sys.stdin.readline().split())
Edges = [None] * E

for i in range(E):
    si, ti, di = map(int, sys.stdin.readline().split())
    Edges[i] = (si, ti, di)
    
ans = Bellmanford(V, Edges, R)

print(*ans, sep = '\n')

Solution (Python):
import sys

INF = float('inf')

def Bellmanford(n, edges, r): 
    d = [INF] * n
    d[r] = 0
    
    for i in range(n):
        
        for (u, v, c) in edges:
            if d[u] != INF and d[u] + c < d[v]:
                d[v] = d[u] + c
                if i == n-1:
                    return ['NEGATIVE CYCLE']
    
    d = [di if di < INF else 'INF' for di in d]
    return d
    

V, E, R = map(int, sys.stdin.readline().split())
Edges = [None] * E

for i in range(E):
    si, ti, di = map(int, sys.stdin.readline().split())
    Edges[i] = (si, ti, di)
    
ans = Bellmanford(V, Edges, R)

print(*ans, sep = '\n')

Solution (Python):
from collections import defaultdict
v_num, e_num, source = (int(n) for n in input().split(" "))
conn = []
cost = [float("inf") for n in range(v_num)]
cost[source] = 0
for _ in range(e_num):
    s1, t1, weight = (int(n) for n in input().split(" "))
    conn.append([s1, t1, weight])

def bellman_ford(source, conn, v_num, cost):
    for i in range(v_num):
        for s, t, weight in conn:
            if cost[t] > cost[s] + weight:
                if i == v_num - 1:
                    return True
                cost[t] = cost[s] + weight
    return False

if bellman_ford(source, conn, v_num, cost):
    print("NEGATIVE CYCLE")
else:
    cost = ["INF" if n == float("inf") else n for n in cost]
    for c in cost:
        print(c)

Solution (Python):

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

"""
import sys
from sys import stdin
from collections import namedtuple
input = stdin.readline


def shortest_path(es, V, s):
    count = 0
    d = [float('inf')] * V
    d[s] = 0

    while True:
        update = False
        count += 1

        if count > V:
            return None

        for e in es:
            if d[e.f] != float('inf') and d[e.t] > d[e.f] + e.c:
                d[e.t] = d[e.f] + e.c
                update = True
        if update is False:
            break

    for i, dist in enumerate(d):
        if dist == float('inf'):
            d[i] = 'INF'
    return d


edge = namedtuple('edge', ['f', 't', 'c'])
def main(args):
    V, E, r = map(int, input().split())
    es = []
    for _ in range(E):
        s, t, d = map(int, input().split())
        es.append(edge(s, t, d))

    result = shortest_path(es, V, r)

    if result is None:
        print('NEGATIVE CYCLE')
    else:
        print('\n'.join(map(str, result)))


if __name__ == '__main__':
    main(sys.argv[1:])

Solution (Python):

def inpl(): return tuple(map(int, input().split()))
INF = float("inf")
V, E, r = inpl()

edges = [inpl() for _ in range(E)]

def belman_ford(V, edges, r):
    "If glaph contains negative cycles then return True"
    D = [INF]*(V)
    D[r] = 0
    if V == 1:
        return False, [0]
    
    for _ in range(V-1):
        update = False
        for s, t, d in edges:
            if D[t] > D[s] + d:
                D[t] = D[s] + d
                update = True
        if not update:
            break
    else:
        return True, D
    return False, D
    
NEGATIVE, D = belman_ford(V, edges, r)

if NEGATIVE:
    print("NEGATIVE CYCLE")
else:
    for d in D:
        print("INF") if d == INF else print(d)

Solution (Python):

def inpl(): return tuple(map(int, input().split()))
INF = float("inf")
V, E, r = inpl()

edges = [inpl() for _ in range(E)]

def belman_ford(V, edges, r):
    D = [INF]*(V)
    D[r] = 0
    if V == 1:
        return [0], [False]
    
    for _ in range(V):
        update = False
        for s, t, d in edges:
            if D[t] > D[s] + d:
                D[t] = D[s] + d
                update = True
        if not update:
            break
    else:
        NEGATIVE = [False]*(V)
        for s, t, d in edges:
            if D[t] > D[s] + d:
                D[t] = D[s] + d
                NEGATIVE[t] = True
                NEGATIVE[s] = True
        return D, NEGATIVE
                
    return D, [False]*(V)
    
D, NEGATIVE = belman_ford(V, edges, r)

if any(NEGATIVE):
    print("NEGATIVE CYCLE")
else:
    for d in D:
        print("INF") if d == INF else print(d)

Solution (Python):
import queue


class Edge:
    def __init__(self, _to, _cost):
        self.to = _to
        self.cost = _cost


def bellman(n, graph, start):
    dist = [0 if i == start else float('inf') for i in range(n)]

    for i in range(n):
        for v in range(n):
            for e in graph[v]:
                if dist[v] == float('inf') or dist[e.to] <= dist[v] + e.cost:
                    continue

                dist[e.to] = dist[v] + e.cost

                if i == n - 1:
                    return None

    return dist


def main():
    n, m, s = map(int, input().split())
    graph = [[] for _ in range(n)]

    for _ in range(m):
        data = list(map(int, input().split()))

        graph[data[0]].append(Edge(data[1], data[2]))

    ans = bellman(n, graph, s)

    if ans is None:
        print("NEGATIVE CYCLE")
    else:
        for i in range(n):
            print(ans[i] if ans[i] != float('inf') else "INF")
        return


if __name__ == '__main__':
    main()

Solution (Python):
import queue


class Edge:
    def __init__(self, _to, _cost):
        self.to = _to
        self.cost = _cost


def bellman(n, graph, start):
    dist = [0 if i == start else float('inf') for i in range(n)]

    for i in range(n):
        for v in range(n):
            for e in graph[v]:
                if dist[v] == float('inf') or dist[e.to] <= dist[v] + e.cost:
                    continue

                dist[e.to] = dist[v] + e.cost

                if i == n - 1:
                    return None

    return dist


def main():
    n, m, s = map(int, input().split())
    graph = [[] for _ in range(n)]

    for _ in range(m):
        data = list(map(int, input().split()))

        graph[data[0]].append(Edge(data[1], data[2]))

    ans = bellman(n, graph, s)

    if ans is None:
        print("NEGATIVE CYCLE")
    else:
        for i in range(n):
            print(ans[i] if ans[i] != float('inf') else "INF")
        return


if __name__ == '__main__':
    main()

Solution (Python):
v, e, r = map(int, input().split())
a = []
for i in range(e):
    A = list(map(int, input().split()))
    a.append(A)

costs = [None] * v
costs[r] = 0
count = 0
while True:
    count += 1
    update = False
    for s, t, d in a:
        if costs[s] is None:
            continue
        cost = costs[s] + d
        if costs[t] is None or costs[t] > cost:
            costs[t] = cost
            update = True
    if not update:
        for cost in costs:
            print("INF" if cost is None else cost)
        break
    if count == v:
        print("NEGATIVE CYCLE")
        break

Solution (Python):
"""
BellmanFord
"""

INF = 10 ** 20

v_num, e_num, r = map(int, input().split())
dist_lst = [INF for _ in range(v_num)]
edges_lst = [[] for _ in range(e_num)]
negative_cycle_flag = False

for _ in range(e_num):
  s, t, dist = map(int, input().split())
  edges_lst[s].append((dist, t))

dist_lst[r] = 0

if e_num != 0:
  for _ in range(v_num):
    for v in range(v_num):
      if dist_lst[v] != INF:
        for dist, to in edges_lst[v]:
          if dist_lst[v] + dist < dist_lst[to]:
            dist_lst[to] = dist_lst[v] + dist
  
  for v in range(v_num):
    if dist_lst[v] != INF:
      for dist, to in edges_lst[v]:
        if dist_lst[v] + dist < dist_lst[to]:
          negative_cycle_flag = True
          break
      if negative_cycle_flag:
        break

if negative_cycle_flag:
  print("NEGATIVE CYCLE")
else:
  for dist in dist_lst:
    if dist == INF:
      print("INF")
    else:
      print(dist)