Problem:
All Pairs Shortest Path Input An edge-weighted graph G ( V , E ). | V | | E | 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.  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), print NEGATIVE CYCLE  in a line.  Otherwise, print   D 0,0  D 0,1 ... D 0,|V|-1  D 1,0  D 1,1 ... D 1,|V|-1 : D |V|-1,0  D 1,1 ... D |V|-1,|V|-1   The output consists of |V| lines. For each i th line, print the cost of the shortest path from vertex i to each vertex j ( j = 0, 1, ... |V|-1 ) respectively. If there is no path from vertex i to vertex j , print " INF ". Print a space between the costs.  Constraints   1 ≤ |V| ≤ 100  0 ≤ |E| ≤ 9900  -2 × 10 7 ≤ d i ≤ 2 × 10 7  There are no parallel edges  There are no self-loops   Sample Input 1  4 6
0 1 1
0 2 5
1 2 2
1 3 4
2 3 1
3 2 7  Sample Output 1  0 1 3 4
INF 0 2 3
INF INF 0 1
INF INF 7 0   Sample Input 2  4 6
0 1 1
0 2 -5
1 2 2
1 3 4
2 3 1
3 2 7  Sample Output 2  0 1 -5 -4
INF 0 2 3
INF INF 0 1
INF INF 7 0   Sample Input 3  4 6
0 1 1
0 2 5
1 2 2
1 3 4
2 3 1
3 2 -7  Sample Output 3  NEGATIVE CYCLE

Solution (Python):
class exist_negative_cycle(Exception):
    pass
def warshall_floyd(g, size):
    d = [[float('inf')] * size for _ in range(size)]

    for i in range(size):
        d[i][i] = 0

    for u in g:
        for length, v in g[u]:
            d[u][v] = length

    for k in range(size):
        for i in range(size):
            for j in range(size):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
    for i in range(size):
        if d[i][i] < 0:
            raise exist_negative_cycle
    return d


from collections import defaultdict
from sys import stdin
import math
readline = stdin.readline

v, e = map(int, readline().split())
g = defaultdict(list)
for i in range(e):
    s, t, length = map(int, readline().split())
    g[s].append((length, t))
try:
    d = warshall_floyd(g, v)
    for di in d:
        print(' '.join(['INF' if math.isinf(dij) else str(dij) for dij in di]))
except exist_negative_cycle:
    print('NEGATIVE CYCLE')

Solution (Python):
def warshall_floyd(graph, edges):
    N = len(graph)
    inf = Infinity()  
    for i in xrange(N):
        for j in xrange(N):
            if i == j:
                graph[i][j] = 0
            else:
                graph[i][j] = inf
    for e in edges:
        graph[e.source][e.destination] = e.weight
    for k in xrange(N):
        for i in xrange(N):
            for j in xrange(N):
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
    for k in xrange(N):
        for i in xrange(N):
            for j in xrange(N):
                if inf in (graph[i][j], graph[i][k], graph[k][j]):  
                    continue
                if graph[i][j] > graph[i][k] + graph[k][j]:
                    raise NegativeCycleError

def main():
    V, E = map(int, raw_input().split())
    graph = [[None] * V for _ in xrange(V)]
    edges = []
    for _ in xrange(E):
        s, t, d = map(int, raw_input().split())
        edges.append(Edge(s, t, d))
    try:
        warshall_floyd(graph, edges)
        for g in graph:
            print " ".join(map(str, g))
    except NegativeCycleError:
        print "NEGATIVE CYCLE"

class Infinity(object):
    def __eq__(self, other):
        return other is self

    def __lt__(self, other):
        return False

    def __gt__(self, other):
        return True

    def __add__(self, other):
        return self

    def __radd__(self, other):
        return self

    def __str__(self):
        return "INF"
    __repr__ = __str__

class NegativeCycleError(Exception):
    pass

class Edge(object):
    def __init__(self, source, destination, weight):
        self.source = source
        self.destination = destination
        self.weight = weight

if __name__ == "__main__":
    main()

Solution (Python):
def warshall_floyd(graph, edges):
    N = len(graph)
    for i in xrange(N):
        for j in xrange(N):
            if i == j:
                graph[i][j] = 0
            else:
                graph[i][j] = Infinity()
    for e in edges:
        graph[e.source][e.destination] = e.weight
    for k in xrange(N):
        for i in xrange(N):
            for j in xrange(N):
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
    for i in xrange(N):
        if graph[i][i] < 0:
            raise NegativeCycleError

def main():
    V, E = map(int, raw_input().split())
    graph = [[None] * V for _ in xrange(V)]
    edges = []
    for _ in xrange(E):
        s, t, d = map(int, raw_input().split())
        edges.append(Edge(s, t, d))
    try:
        warshall_floyd(graph, edges)
        for g in graph:
            print " ".join(map(str, g))
    except NegativeCycleError:
        print "NEGATIVE CYCLE"

class Infinity(object):
    def __eq__(self, other):
        return other is self

    def __lt__(self, other):
        return False

    def __gt__(self, other):
        return True

    def __add__(self, other):
        return self

    def __radd__(self, other):
        return self

    def __str__(self):
        return "INF"
    __repr__ = __str__

class NegativeCycleError(Exception):
    pass

class Edge(object):
    def __init__(self, source, destination, weight):
        self.source = source
        self.destination = destination
        self.weight = weight

if __name__ == "__main__":
    main()

Solution (Python):
from heapq import heapify, heappush, heappop
from collections import Counter, defaultdict, deque, OrderedDict
from sys import setrecursionlimit as setreclim
from sys import maxsize
from bisect import bisect_left, bisect, insort_left, insort
from math import ceil, log, factorial, hypot, pi
from fractions import gcd
from copy import deepcopy
from functools import reduce
from operator import mul
from itertools import product, permutations, combinations, accumulate, cycle
from string import ascii_uppercase, ascii_lowercase, ascii_letters, digits, hexdigits, octdigits

prod = lambda l: reduce(mul, l)
prodmod = lambda l, mod: reduce(lambda x, y: mul(x,y)%mod, l)

class WarshallFloyd():
    """Warshall-Floyd Algorithm: 
       find the lengths of the shortest paths between all pairs of vertices
    """

    def __init__(self, V, E, INF=10**9):
        """ V: the number of vertexes
            E: adjacency list
            start: start vertex
            INF: Infinity distance
        """
        self.V = V
        self.E = E
        self.warshall_floyd(INF)

    def warshall_floyd(self, INF):
        self.distance = [[INF] * self.V for _ in range(V)]
        for i in range(V): self.distance[i][i] = 0
        for fr in range(V):
            for to, cost in self.E[fr]:
                self.distance[fr][to] = cost
        for k in range(self.V):
            for i in range(self.V):
                for j in range(self.V):
                    if self.distance[i][k] != INF and self.distance[k][j] != INF:
                        self.distance[i][j] = min(self.distance[i][j], self.distance[i][k] + self.distance[k][j])

    def hasNegativeCycle(self):
        for i in range(V):
            if self.distance[i][i] < 0:
                return True
        else:
            return False
                
V, E = map(int, input().split())
INF = 10**10
edge = [[] for _ in range(V)]

for i in range(E):
    s, t, cost = map(int, input().split())
    edge[s].append((t, cost))

allsp = WarshallFloyd(V, edge, INF)
            
if allsp.hasNegativeCycle():
    print('NEGATIVE CYCLE')
else:
    for dist in allsp.distance:
        print(*[d if d != INF else 'INF' for d in dist])

Solution (Python):
V, E = map(int, raw_input().split())
G = [[float("inf")] * V for i in xrange(V)]
for i in xrange(V):
    G[i][i] = 0
for i in xrange(E):
    s, t, d = map(int, raw_input().split())
    G[s][t] = d

for k in xrange(V):
    for i in xrange(V):
        for j in xrange(V):
            G[i][j] = min(G[i][j], G[i][k] + G[k][j])

for i in xrange(V):
    if G[i][i] < 0:
        print "NEGATIVE CYCLE"
        exit()
    for j in xrange(V):
        if G[i][j] == float("inf"):
            G[i][j] = "INF"

for line in G:
    print " ".join(map(str, line))

Solution (Python):

from math import isinf


def main():
    V, E = map(int, input().split())
    D = [[float('inf')] * V for _ in range(V)]

    for i in range(V):
        D[i][i] = 0

    for i in range(E):
        s, t, d = map(int, input().split())
        D[s][t] = d

    for k in range(V):
        for i in range(V):
            for j in range(V):
                if D[i][j] > D[i][k] + D[k][j]:
                    D[i][j] = D[i][k] + D[k][j]

    for i in range(V):
        if D[i][i] < 0:
            print("NEGATIVE CYCLE")
            return

    for di in D:
        print(' '.join(('INF' if isinf(dij) else str(dij) for dij in di)))

main()

Solution (Python):
from __future__ import division
from collections import defaultdict, deque
from heapq import heappush, heappop
from sys import stdin

class UnionFindSet:
	def __init__(self, nodes):
		self.fa = {}
		for n in nodes:
			self.fa[n] = n

	def find(self, x):
		if self.fa[x] == x:
			return x
		else:
			self.fa[x] = self.find(self.fa[x])
			return self.fa[x]

	def union(self, x, y):
		fx = self.find(x)
		fy = self.find(y)
		if fx == fy:
			return fx
		else:
			self.fa[fx] = fy
			return fy


"""
graph is a hash
graph["nodes"] is a list of all nodes in the graph
graph["edges"] is a list of all edges in the graph in (x, y, w) form
  - x is the first nodes
  - y is the second nodes
  - w is the weight of the edges
graph["relation"] is the graph relation of the graph
"""

def kruscal(graph):
	"kruscal minimum spanning tree algorithm"
	ufset = UnionFindSet(graph["nodes"])

	ret = 0

	for (x, y, w) in sorted(graph["edges"], key = lambda x: x[-1]):
		fx = ufset.find(x)
		fy = ufset.find(y)
		if fx != fy:
			ret += w
			ufset.union(fx, fy)
		else:
			pass
	return ret


def dijkstra(graph, root):
	"dijkstra algorithm for single source shortest algorithm"
	dis, vis = {}, {}
	for n in graph["nodes"]:
		dis[n] = 10 ** 9
		vis[n] = False

	heap = []
	dis[root] = 0
	heappush(heap, (0, root))

	while heap:
		_, n = heappop(heap)
		vis[n] = True
		for (y, w) in graph["adj"][n]:
			if not vis[y] and dis[n] + w < dis[y]:
				dis[y] = dis[n] + w
				heappush(heap, (dis[y], y))

	return dis

def belmanFord(graph, root):
	"belman ford algorithm for graph with negative edges"
	dis = {}
	for n in graph["nodes"]:
		dis[n] = 10 ** 9

	dis[root] = 0

	
	for _ in range(len(graph["nodes"]) - 1):
		for (x, y, w) in graph["edges"]:
			if dis[x] + w < dis[y]:
				dis[y] = dis[x] + w

	
	connect = set([root])
	que = deque([root])

	while que:
		n = que.popleft()
		for (y, _) in graph["adj"][n]:
			if not y in connect:
				connect.add(y)
				que.append(y)

	dis["negcicle"] = False
	for (x, y, w) in graph["edges"]:
		if dis[x] + w < dis[y] and x in connect:
			dis["negcicle"] = True

	dis["con"] = connect
	return dis

def floyd(graph):
	n = len(graph["nodes"])
	dis = [[10 ** 20 for _ in range(n)] for _ in range(n)]
	for i in range(n): dis[i][i] = 0

	for x in graph["nodes"]:
		for (y, w) in graph["adj"][x]:
			dis[x][y] = w


	for k in range(n):
		for i in range(n):
			for j in range(n):
				if dis[i][k] < 10 ** 20 and dis[k][j] < 10 ** 20:
					dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])

	return dis


if __name__ == '__main__':
	V, E= map(int, stdin.readline().strip().split())
	graph = {}
	graph["nodes"] = [i for i in range(V)]
	graph["edges"] = []
	graph["adj"] = defaultdict(list)
	for _ in range(E):
		x, y, w = map(int, stdin.readline().strip().split())
		graph["edges"].append((x, y, w))
		graph["adj"][x].append((y, w))

	dis = floyd(graph)

	negcycle = False

	for i in range(len(graph["nodes"])):
		if dis[i][i] < 0:
			negcycle = True

	if negcycle:
		print "NEGATIVE CYCLE"
	else:
		for row in dis:
			print ' '.join(map(lambda x: str(x) if x < 10 ** 20 else "INF", row))

Solution (Python):
from __future__ import division
from collections import defaultdict, deque
from heapq import heappush, heappop
from sys import stdin


def floyd(graph):
    n = len(graph["nodes"])
    dis = [[10 ** 20 for _ in range(n)] for _ in range(n)]
    for i in range(n): dis[i][i] = 0

    for x in graph["nodes"]:
        for (y, w) in graph["adj"][x]:
            dis[x][y] = w


    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dis[i][k] < 10 ** 20 and dis[k][j] < 10 ** 20:
                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])

    return dis


if __name__ == '__main__':
    V, E= map(int, stdin.readline().strip().split())
    graph = {}
    graph["nodes"] = [i for i in range(V)]
    graph["edges"] = []
    graph["adj"] = defaultdict(list)
    for _ in range(E):
        x, y, w = map(int, stdin.readline().strip().split())
        graph["edges"].append((x, y, w))
        graph["adj"][x].append((y, w))

    dis = floyd(graph)

    negcycle = False

    for i in range(len(graph["nodes"])):
        if dis[i][i] < 0:
            negcycle = True

    if negcycle:
        print "NEGATIVE CYCLE"
    else:
        for row in dis:
            print ' '.join(map(lambda x: str(x) if x < 10 ** 20 else "INF", row))

Solution (Python):
from __future__ import division
from collections import defaultdict, deque
from heapq import heappush, heappop
from sys import stdin


def floyd(graph):
    n = len(graph["nodes"])
    dis = [[10 ** 20 for _ in range(n)] for _ in range(n)]
    for i in range(n): dis[i][i] = 0

    for x in graph["nodes"]:
        for (y, w) in graph["adj"][x]:
            dis[x][y] = w


    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dis[i][k] < 10 ** 20 and dis[k][j] < 10 ** 20:
                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])

    return dis


if __name__ == '__main__':
    V, E= map(int, stdin.readline().strip().split())
    graph = {}
    graph["nodes"] = [i for i in range(V)]
    graph["edges"] = []
    graph["adj"] = defaultdict(list)
    for _ in range(E):
        x, y, w = map(int, stdin.readline().strip().split())
        graph["edges"].append((x, y, w))
        graph["adj"][x].append((y, w))

    dis = floyd(graph)

    negcycle = False

    for i in range(len(graph["nodes"])):
        if dis[i][i] < 0:
            negcycle = True

    if negcycle:
        print "NEGATIVE CYCLE"
    else:
        for row in dis:
            print ' '.join(map(lambda x: str(x) if x < 10 ** 20 else "INF", row))

Solution (Python):
from __future__ import division
from collections import defaultdict, deque
from heapq import heappush, heappop
from sys import stdin


def floyd(graph):
    n = len(graph["nodes"])
    dis = [[10 ** 20 for _ in range(n)] for _ in range(n)]
    for i in range(n): dis[i][i] = 0

    for x in graph["nodes"]:
        for (y, w) in graph["adj"][x]:
            dis[x][y] = w


    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dis[i][k] < 10 ** 20 and dis[k][j] < 10 ** 20:
                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])

    return dis


if __name__ == '__main__':
    V, E= map(int, stdin.readline().strip().split())
    graph = {}
    graph["nodes"] = [i for i in range(V)]
    graph["edges"] = []
    graph["adj"] = defaultdict(list)
    for _ in range(E):
        x, y, w = map(int, stdin.readline().strip().split())
        graph["edges"].append((x, y, w))
        graph["adj"][x].append((y, w))

    dis = floyd(graph)

    negcycle = False

    for i in range(len(graph["nodes"])):
        if dis[i][i] < 0:
            negcycle = True

    if negcycle:
        print "NEGATIVE CYCLE"
    else:
        for row in dis:
            print ' '.join(map(lambda x: str(x) if x < 10 ** 20 else "INF", row))

Solution (Python):
INF = 1<<31
V, E = map(int, raw_input().split())
l = [[INF]*V for i in range(V)]
for i in xrange(E):
    s, t, d = map(int, raw_input().split())
    l[s][t] = d
for k in range(V):
    for i in range(V):
        for j in range(V):
            if l[i][k] != INF and l[k][j] != INF:
                l[i][j] = min(l[i][j], l[i][k] + l[k][j])
for i in range(V):
    if l[i][i] < 0:
        print "NEGATIVE CYCLE"
        break
    l[i][i] = 0
else:
    for r in l:
        for i in range(V):
            if r[i] == INF: r[i] = "INF"
        print " ".join(map(str, r))

Solution (Python):
INF = float("inf")
V, E = map(int, raw_input().split())
l = [[INF]*V for i in range(V)]
for i in xrange(E):
    s, t, d = map(int, raw_input().split())
    l[s][t] = d
for k in range(V):
    for i in range(V):
        for j in range(V):
            l[i][j] = min(l[i][j], l[i][k] + l[k][j])
for i in range(V):
    if l[i][i] < 0:
        print "NEGATIVE CYCLE"
        break
    l[i][i] = 0
else:
    for r in l:
        for i in range(V):
            if r[i] == INF: r[i] = "INF"
        print " ".join(map(str, r))

Solution (Python):
V, E = map(int, input().split())
dist = [[float('inf') for j in range(V)] for i in range(V)]
for i in range(V):
    dist[i][i] = 0
for i in range(E):
    s, t, d = map(int, input().split())
    dist[s][t] = d

negative_cycle = False

for k in range(V):
    for i in range(V):
        for j in range(V):
            if dist[i][k] == float('inf') or dist[k][j] == float('inf'):
                continue
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]

for i in range(V):
    if dist[i][i] < 0:
        negative_cycle = True

if negative_cycle:
    print('NEGATIVE CYCLE')
else:
    for i in range(V):
        d = ['INF' if e == float('inf') else e for e in  dist[i]]
        print(*d)

Solution (Python):
nv, ne = map(int, input().split())

costs = [[None] * nv for _ in range(nv)]
for i in range(nv):
    costs[i][i] = 0

while ne:
    s, t, d = map(int, input().split())
    costs[s][t] = d
    ne -= 1


def loop():
    for k in range(nv):
        for i in range(nv):
            for j in range(nv):
                if costs[i][k] is None or costs[k][j] is None:
                    continue
                tmp_cost = costs[i][k] + costs[k][j]
                if i == j and tmp_cost < 0:
                    print('NEGATIVE CYCLE')
                    return False
                if costs[i][j] is None or costs[i][j] > tmp_cost:
                    costs[i][j] = tmp_cost
    return True


if loop():
    for vc in costs:
        print(*('INF' if c is None else c for c in vc))

Solution (Python):
v,e=map(int,raw_input().split())
glist=[[float('inf')]*v for i in xrange(v)]
A=[[0]*v for i in xrange(v)]
negativect=0
for i in xrange(e):
    s,t,d=map(int,raw_input().split())
    glist[s][t]=d
for i in xrange(v):
    for j in xrange(v):
        if i==j:
            A[i][j]=0
        else:
            A[i][j]=glist[i][j]
for k in xrange(v):
    for i in xrange(v):
        for j in xrange(v):
            A[i][j]=min(A[i][j],A[i][k]+A[k][j])
for i in xrange(v):
    for j in xrange(v):
        if A[i][j]==float('inf'):
            A[i][j]='INF'
        if i==j and A[i][j]<0:
            negativect+=1
        A[i][j]=str(A[i][j])
if negativect>0:
    print('NEGATIVE CYCLE')
else:
    for i in xrange(v):
        print(" ".join(A[i]))

Solution (Python):
INF = 10**18

V, E = map(int, raw_input().split())
cost = [[INF]*V for i in xrange(V)]
for i in xrange(E):
    s, t, d = map(int, raw_input().split())
    cost[s][t] = d
for i in xrange(V):
    cost[i][i] = 0

for k in xrange(V):
    for i in xrange(V):
        for j in xrange(V):
            if cost[i][k]!=INF and cost[k][j]!=INF:
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])
if any(cost[i][i]<0 for i in xrange(V)):
    print "NEGATIVE CYCLE"
else:
    print "\n".join(" ".join(map(lambda e: str(e) if e<INF else "INF", e)) for e in cost)

Solution (Python):
def print_solve(ans):
    if "negative" in ans:
        print("NEGATIVE CYCLE")
    else:
        for l in ans:
            for c in l[:-1]:
                if c == float("inf"):
                    print("INF",end=" ")
                else:
                    print(c,end=" ")
            if l[-1] == float("inf"):
                print("INF")
            else:
                print(l[-1])

def solve(graph_data, num_v):
    ans = []

    for i in range(num_v):
        ans.append(partial_solve(graph_data, i, num_v))

    return ans

def partial_solve(graph_data, source, num_v):
    ans = [0 if i == source else float('inf') for i in range(num_v)]

    i = 0
    while (ans != solver_iteration(graph_data, ans)):
        ans = solver_iteration(graph_data, ans)
        i += 1
        if i >= num_v:
            return "negative"

    return ans

def solver_iteration(graph_data, prev_ans):
    new_ans = prev_ans[0:]

    for i, v in enumerate(new_ans):
        if v == float('inf') or i not in graph_data:
            continue

        for t, w in graph_data[i]:
                new_ans[t] = min(new_ans[t], v + w)

    return new_ans

def main():
    l = input().split()
    V = int(l[0])
    E = int(l[1])

    graph = {}
    for i in range(E):
        l = input().split()
        s = int(l[0])
        t = int(l[1])
        d = int(l[2])

        if s in graph:
            graph[s].append((t,d))
        else:
            graph[s] = [(t,d)]

    print_solve(solve(graph, V))

if __name__ == "__main__":
    main()

Solution (Python):
import sys

def warshall(n, matrix):
  for i in xrange(n):
    matrix[i][i] = 0
  for i in xrange(n):
    for j in xrange(n):
      for k in xrange(n):
        matrix[j][k] = min(matrix[j][k], matrix[j][i]+matrix[i][k])
  return matrix

V,E = map(int, raw_input().split())
path = [[sys.maxint] * V for _ in xrange(V)]
for _ in xrange(E):
  s,t,d = map(int, raw_input().split())
  path[s][t] = d
cost = warshall(V, path)
isNegative = False
for i in xrange(V):
  if cost[i][i] < 0:
    isNegative = True
    break

if isNegative:
  print "NEGATIVE CYCLE"
else:
  for i in xrange(V):
    printlist = []
    for j in xrange(V):
      if cost[i][j] > 10 ** 12:
        printlist.append("INF")
      else:
        printlist.append(str(cost[i][j]))
    print " ".join(printlist)

Solution (Python):
import sys

f_i = sys.stdin

max_d = float("inf")

V, E = map(int, f_i.readline().split())


A = [[max_d] * i + [0] + [max_d] * (V - i - 1) for i in range(V)]

for l_i in f_i:
    s, t, d = map(int, l_i.split())
    A[s][t] = d


for k in range(V - 1):
    for i in range(V):
        for j in range(V):
            A[i][j] = min(A[i][j], A[i][k] + A[k][j])

for i in range(V):
    for j in range(V):
        e = min(A[i][j], A[i][V - 1] + A[V - 1][j])
        if e == max_d:
            A[i][j] = "INF"
        else:
            A[i][j] = e



flag = 1
for k in range(V):
    if A[k][k] < 0:
        flag = 0
        print("NEGATIVE CYCLE")
        break


if flag:
    for a in A:
        print(*a)

Solution (Python):
import sys

f_i = sys.stdin

max_d = float("inf")

V, E = map(int, f_i.readline().split())


A = [[max_d] * i + [0] + [max_d] * (V - i - 1) for i in range(V)]

for l_i in f_i:
    s, t, d = map(int, l_i.split())
    A[s][t] = d



for k in range(V):
    for i in range(V):
        for j in range(V):
            A[i][j] = min(A[i][j], A[i][k] + A[k][j])


is_negative = 0
for k in range(V):
    if A[k][k] < 0:
        is_negative = 1
        print("NEGATIVE CYCLE")
        break


if not is_negative:
    for a in A:
        print(*[str(e).upper() for e in a])

Solution (Python):
import sys

f_i = sys.stdin

max_d = float("inf")

V, E = map(int, f_i.readline().split())


A = [[max_d] * i + [0] + [max_d] * (V - i - 1) for i in range(V)]

for l_i in f_i:
    s, t, d = map(int, l_i.split())
    A[s][t] = d



for k in range(V):
    for i in range(V):
        for j in range(V):
            A[i][j] = min(A[i][j], A[i][k] + A[k][j])


is_negative = 0
for k in range(V):
    if A[k][k] < 0:
        is_negative = 1
        print("NEGATIVE CYCLE")
        break


import math

if not is_negative:
    for a in A:
        print(' '.join(('INF' if math.isinf(Aij) else str(Aij) for Aij in a)))

Solution (Python):



from sys import stdin


def generate_adj_table(v_table):
    for each in v_table:
        start, end, weight = map(int, each)
        init_adj_table[start][end] = weight

    return init_adj_table


def floyd():
    for k in _range:
        for i in _range:
            for j in _range:
                adj_table[i][j] = min(adj_table[i].get(j, float("INF")),
                                      adj_table[i].get(k, float("INF")) + adj_table[k].get(j, float("INF")))
    return adj_table


def solve():
    ans = floyd()
    negative = False
    for m in range(vertices):
        if ans[m][m] < 0:
            negative = True

    if negative:
        print('NEGATIVE CYCLE')
    else:
        for a in _range:
            print(*(str(each[-1]).upper() for each in sorted(ans[a].items())))

    return None


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

    init_adj_table = tuple({i: 0} for i in range(vertices))
    adj_table = generate_adj_table(info_list)
    solve()

Solution (Python):



from sys import stdin
from math import isinf


def generate_adj_table(v_table, _init_adj_table):
    for each in v_table:
        start, end, weight = map(int, each)
        _init_adj_table[start][end] = weight

    return _init_adj_table


def floyd(_adj_table):
    for k in _range:
        for i in _range:
            for j in _range:
                _adj_table[i][j] = min(_adj_table[i][j],
                                       _adj_table[i][k] + _adj_table[k][j])
    return _adj_table


def solve(_adj_table):
    after_floyd_table = floyd(_adj_table)

    negative = False
    for m in _range:
        if after_floyd_table[m][m] < 0:
            negative = True

    if negative:
        print('NEGATIVE CYCLE')
        return None
    else:
        for each in after_floyd_table:
            print(' '.join(('INF' if isinf(ele) else str(ele) for ele in each)))

    return after_floyd_table


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

    init_adj_table = tuple([float('inf')] * vertices for i in range(vertices))
    for n in _range:
        init_adj_table[n][n] = 0

    adj_table = generate_adj_table(info_list, init_adj_table)
    solve(adj_table)

Solution (Python):



from sys import stdin
from math import isinf


def generate_adj_table(v_table, _init_adj_table):
    for each in v_table:
        start, end, weight = map(int, each)
        _init_adj_table[start][end] = weight

    return _init_adj_table


def floyd(_adj_table):
    for k in v_range:
        for i in v_range:
            for j in v_range:
                _adj_table[i][j] = min(_adj_table[i][j],
                                       _adj_table[i][k] + _adj_table[k][j])
    return _adj_table


def solve(_after_table):
    negative = False
    for m in v_range:
        if _after_table[m][m] < 0:
            negative = True

    if negative:
        print('NEGATIVE CYCLE')
        return None
    else:
        for each in _after_table:
            print(' '.join(('INF' if isinf(ele) else str(ele) for ele in each)))

    return _after_table


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

    init_adj_table = tuple([float('inf')] * vertices for _ in v_range)
    for n in v_range:
        init_adj_table[n][n] = 0

    adj_table = generate_adj_table(info_list, init_adj_table)
    after_table = floyd(adj_table)
    solve(after_table)

Solution (Python):



from sys import stdin
from math import isinf


def generate_adj_table(v_table, _init_adj_table):
    for each in v_table:
        start, end, weight = map(int, each)
        _init_adj_table[start][end] = weight

    return _init_adj_table


def floyd(_adj_table):
    for k in v_range:
        for i in v_range:
            for j in v_range:
                _adj_table[i][j] = min(_adj_table[i][j],
                                       _adj_table[i][k] + _adj_table[k][j])
    return _adj_table


def solve(_after_table):
    negative = False
    for m in v_range:
        if _after_table[m][m] < 0:
            negative = True

    if negative:
        print('NEGATIVE CYCLE')
        return None
    else:
        for each in _after_table:
            print(' '.join(('INF' if isinf(ele) else str(ele) for ele in each)))

    return _after_table


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

    init_adj_table = tuple([float('inf')] * vertices for _ in v_range)
    for n in v_range:
        init_adj_table[n][n] = 0

    adj_table = generate_adj_table(info_list, init_adj_table)
    after_table = floyd(adj_table)
    ans = solve(after_table)

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

dist = [[float('inf')] * nv for i in range(nv)]
for i in range(nv):
    dist[i][i] = 0
for s, t, w in edges:
    dist[s][t] = w

for k in range(nv):
    for i in range(nv):
        for j in range(nv):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]

for i in range(nv):
    if dist[i][i] < 0:
        print("NEGATIVE CYCLE")
        exit()

for row in dist:
    print(' '.join(str(d) if d < float('inf') else 'INF' for d in row))

Solution (Python):
from collections import defaultdict

vertice,edge = map(int,input().split(" "))
cost = [[0 if m == n else float("inf") for n in range(vertice)] for m in range(vertice)]
link = defaultdict(dict)
weight = defaultdict(dict)

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 1:
    if vertice_cnt >= vertice:
        print("NEGATIVE CYCLE")
        break
    update = False
    for source in range(vertice):
        for k,value in link.items():
            for v in value:
                if cost[source][v] > cost[source][k] + weight[k][v]:
                    cost[source][v] = cost[source][k] + weight[k][v]
                    update = True
    if not update:
        for o in range(vertice):

            print(*([n if n != float("INF") else "INF" for n in cost[o]]))
        break
    vertice_cnt += 1