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

def warshall_floyd(v_count, matrix):
    for i in range(v_count):
        for j in range(v_count):
            c2 = matrix[j][i]
            for k, (c1, c3) in enumerate(zip(matrix[j], matrix[i])):
                if c1 > c2+c3:
                    matrix[j][k] = c2+c3
    return matrix


def has_negative_cycle(a) -> bool:
    return any(row[i] < 0 for i, row in enumerate(a))


V, E = map(int, input().split())
inf = float("inf")
matrix = [[inf]*V for _ in [0]*V]
for i in range(V):
    matrix[i][i] = 0
for s, t, d in (map(int, l.split()) for l in sys.stdin):
    matrix[s][t] = d
warshall_floyd(V, matrix)
if has_negative_cycle(matrix):
    print("NEGATIVE CYCLE")
else:
    for row in matrix:
        print(" ".join(map(lambda n: str(n) if n!=inf else "INF", row)))

Solution (Python):
import sys

def warshall_floyd(v_count, matrix):
    for i in range(v_count):
        for j, c2 in enumerate(matrix[j][i] for j in range(v_count)):
            for k, (c1, c3) in enumerate(zip(matrix[j], matrix[i])):
                if c1 > c2+c3:
                    matrix[j][k] = c2+c3
    return matrix


def has_negative_cycle(a) -> bool:
    return any(row[i] < 0 for i, row in enumerate(a))


V, E = map(int, input().split())
inf = float("inf")
matrix = [[inf]*V for _ in [0]*V]
for i in range(V):
    matrix[i][i] = 0
for s, t, d in (map(int, l.split()) for l in sys.stdin):
    matrix[s][t] = d
warshall_floyd(V, matrix)
if has_negative_cycle(matrix):
    print("NEGATIVE CYCLE")
else:
    for row in matrix:
        print(" ".join(map(lambda n: str(n) if n!=inf else "INF", row)))

Solution (Python):
import sys

def warshall_floyd(v_count, matrix):
    for i in range(v_count):
        for j, c2 in enumerate(matrix[j][i] for j in range(v_count)):
            for k, (_, c3) in filter(lambda x: x[1][0] > c2+x[1][1], enumerate(zip(matrix[j], matrix[i]))):
                matrix[j][k] = c2+c3
    return matrix


def has_negative_cycle(a) -> bool:
    return any(row[i] < 0 for i, row in enumerate(a))


V, E = map(int, input().split())
inf = float("inf")
matrix = [[inf]*V for _ in [0]*V]
for i in range(V):
    matrix[i][i] = 0
for s, t, d in (map(int, l.split()) for l in sys.stdin):
    matrix[s][t] = d
warshall_floyd(V, matrix)
if has_negative_cycle(matrix):
    print("NEGATIVE CYCLE")
else:
    for row in matrix:
        print(" ".join(map(lambda n: str(n) if n!=inf else "INF", row)))

Solution (Python):
import sys

def warshall_floyd(v_count, matrix):
    for i in range(v_count):
        for j, c2 in enumerate(matrix[j][i] for j in range(v_count)):
            for k, c1, c3 in zip(range(v_count), matrix[j], matrix[i]):
                if c1 > c2+c3:
                    matrix[j][k] = c2+c3
    return matrix


def has_negative_cycle(a) -> bool:
    return any(row[i] < 0 for i, row in enumerate(a))


V, E = map(int, input().split())
inf = float("inf")
matrix = [[inf]*V for _ in [0]*V]
for i in range(V):
    matrix[i][i] = 0
for s, t, d in (map(int, l.split()) for l in sys.stdin):
    matrix[s][t] = d
warshall_floyd(V, matrix)
if has_negative_cycle(matrix):
    print("NEGATIVE CYCLE")
else:
    for row in matrix:
        print(" ".join(map(lambda n: str(n) if n!=inf else "INF", row)))

Solution (Python):
import sys

def warshall_floyd(v_count: int, matrix: list) -> list:
    """ ワーシャルフロイド
    :param v_count: 頂点数
    :param matrix: 隣接行列
    """
    for i in range(v_count):
        for j, c2 in enumerate(row[i] for row in matrix):
            for k, (c1, c3) in enumerate(zip(matrix[j], matrix[i])):
                if c1 > c2+c3:
                    matrix[j][k] = c2+c3
    return matrix


def has_negative_cycle(matrix: list) -> bool:
    """ 負閉路チェック
    :param matrix: 隣接行列(ワーシャルフロイドの結果)
    """
    return any(row[i] < 0 for i, row in enumerate(matrix))


V, E = map(int, input().split())
inf = float("inf")
matrix = [[inf]*V for _ in [0]*V]
for i in range(V):
    matrix[i][i] = 0
for s, t, d in (map(int, l.split()) for l in sys.stdin):
    matrix[s][t] = d
warshall_floyd(V, matrix)
if has_negative_cycle(matrix):
    print("NEGATIVE CYCLE")
else:
    for row in matrix:
        print(" ".join(map(lambda n: str(n) if n!=inf else "INF", row)))

Solution (Python):
import sys

def warshall_floyd(v_count: int, matrix: list) -> list:
    """ ワーシャルフロイド
    :param v_count: 頂点数
    :param matrix: 隣接行列
    """
    for i in range(v_count):
        for j, c2 in ((j, matrix[j][i]) for j in range(v_count)):
            for k, (c1, c3) in enumerate(zip(matrix[j], matrix[i])):
                if c1 > c2+c3:
                    matrix[j][k] = c2+c3
    return matrix


def has_negative_cycle(matrix: list) -> bool:
    """ 負閉路チェック
    :param matrix: 隣接行列(ワーシャルフロイドの結果)
    """
    return any(row[i] < 0 for i, row in enumerate(matrix))


V, E = map(int, input().split())
inf = float("inf")
matrix = [[inf]*V for _ in [0]*V]
for i in range(V):
    matrix[i][i] = 0
for s, t, d in (map(int, l.split()) for l in sys.stdin):
    matrix[s][t] = d
warshall_floyd(V, matrix)
if has_negative_cycle(matrix):
    print("NEGATIVE CYCLE")
else:
    for row in matrix:
        print(" ".join(map(lambda n: str(n) if n!=inf else "INF", row)))

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

def read_graph(v, e):
    A = [ [float('inf')]*v for _ in range(v) ]
    for i in range(v):
        A[i][i] = 0
    for _ in range(e):
        line = list(stdin.readline().strip().split())
        i = line[0]
        j = line[1]
        k = line[2]
        A[int(i)][int(j)] = int(k)
    return A

def worshall_floyd(A, v):
    for k in range(v):
        for i in range(v):
            if A[i][k] == float('inf'):
                continue
            for j in range(v):
                if A[k][j] == float('inf'):
                    continue
                A[i][j] = min(A[i][j], A[i][k] + A[k][j])
    return A

def print_ans(A, v):
    NEGATIVE = False
    for i in range(v):
        if A[i][i] < 0:
            NEGATIVE = True
    if NEGATIVE:
        print('NEGATIVE CYCLE')
    else:
        for i in A:
            print(*[str(k).upper() for k in i], sep=' ')

v, e = [int(i) for i in input().split()]
A = read_graph(v, e)
A = worshall_floyd(A, v)
print_ans(A, v)

Solution (Python):
from sys import exit
INF = 1<<32
V,E = [int(n) for n in input().split()]
s = [0]*E
t = [0]*E
d = [0]*E
dist = [[INF for _ in range(V)] for __ in range(V)]
for i in range(V):
    dist[i][i]= 0
for i in range(E):
    s[i], t[i], d[i] = [int(n) for n in input().split()]
    dist[s[i]][t[i]] = d[i]

for k in range(V):
    for i in range(V):
        if(dist[i][k]== INF):continue
        for j in range(V):
            if(dist[k][j]== INF):continue
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

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

for i in range(V):
    for j in range(V):
        if j != V-1:
            print(dist[i][j] if dist[i][j] != INF else "INF",end=" ")
        else:
            print(dist[i][j] if dist[i][j] != INF else "INF")

Solution (Python):
import copy

INF = 10**10
v, e = map(int, input().split())
M = [[INF]*v for i in range(v)]
for i in range(v):
    M[i][i] = 0
for i in range(e):
    s, t, d = map(int, input().split())
    M[s][t] = d


ans = copy.deepcopy(M)
for k in range(v):
    for i in range(v):
        if ans[i][k] == INF:
            continue
        for j in range(v):
            if ans[k][j] == INF:
                continue
            
            ans[i][j] = min(ans[i][j], ans[i][k]+ans[k][j])

flag = False
for i in range(v):
    if ans[i][i] < 0:
        flag = True
        break
if flag:
    print('NEGATIVE CYCLE')
else:
    for line in ans:
        line = ['INF' if tmp == INF else tmp for tmp in line]
        print(*line)

Solution (Python):


import sys
from copy import deepcopy

sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
INF=float('inf')


def warshall_floyd(N: int, graph: list) -> list:
    res = deepcopy(graph)
    for i in range(N):
        
        res[i][i] = 0
    
    for k in range(N):
        for i in range(N):
            for j in range(N):
                res[i][j] = min(res[i][j], res[i][k] + res[k][j])
    
    for i in range(N):
        if res[i][i] < 0:
            return []
    return res

N,M=MAP()
G=[[INF]*N for i in range(N)]
for i in range(M):
    s,t,d=MAP()
    G[s][t]=d

ans=warshall_floyd(N, G)

if not len(ans):
    print('NEGATIVE CYCLE')
    exit()
for i in range(N):
    for j in range(N):
        if ans[i][j]==INF:
            ans[i][j]='INF'
for i in range(N):
    print(*ans[i])

Solution (Python):
INF = 999999999999

def BellmanFord_edge(s, v, edge):
    dp = [INF] * v
    dp[s] = 0
    for i in range(0, v):
        dp1 = dp[:]
        for fr, to, d in edge:
            if dp[fr] == INF:
                continue
            if dp[to] > dp[fr] + d:
                dp[to] = dp[fr] + d
                if i == v - 1:
                    return -1
        if dp == dp1:
            break
    return dp

def BellmanFord_graph(s, v, graph):
    dp = [INF] * v
    dp[s] = 0
    for i in range(0, v):
        for k in range(0, v):
            dp1 = [dp[k] + graph[k][j] if dp[k] != INF and graph[k][j] != INF and dp[j] > dp[k] + graph[k][j]
                  else dp[j]
                  for j in range(0, v) ]
            if dp1 != dp and i == v - 1:
                return -1
            dp = dp1
    return dp

dp = []
line = input()
v, e = list(map(int, line.split()))
graph = [ [INF] * v for _ in range(0, v)]
edge = []
for _ in range(0, e):
    line = input()
    s, t, d = list(map(int, line.split()))
    edge += [[s, t, d]]
    graph[s][t] = d
for s in range(0, v):

    dp = BellmanFord_edge(s, v, edge)
    if dp == -1:
        print("NEGATIVE CYCLE")
        break
    else:
        print(" ".join(map(str, [dp[t] if dp[t] != INF else "INF" for t in range(0, v)])))

Solution (Python):
import sys

inf = int(1e12)

def shortestPath(graph):
    n = len(graph)
    dist = [[inf for _ in range(n)] for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    
    for v in range(n):
        for u, cost in graph[v]:
            dist[v][u] = cost

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] != inf and dist[k][j] != inf:
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
                
    return dist

def main():
    v, e = map(int, input().split())
    
    graph = [[] for _ in range(v)]
    
    for i in range(e):
        a, b, cost = map(int, input().split())
        graph[a].append((b, cost))
            
    dist_mat = shortestPath(graph)

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

    for i in range(v):
        output = []
        for j in range(v):
            if dist_mat[i][j] >= inf:
                output.append("INF")
            else:
                output.append(str(dist_mat[i][j]))
        print(" ".join(output))

main()

Solution (Python):

import sys,heapq

INF=2000000000000
def shortestPath(g,dist,prev):
	n = len(g)-1
	h = [INF]*n+[0]
	for k in range(n+1):
		for i in range(n+1):
			for e in g[i]:
				if h[e[1]]<INF and e[0]<INF and h[e[2]] > h[e[1]] + e[0]:
					h[e[2]] = h[e[1]] + e[0]
					if k==n: return False 
	for i in range(n):
		for e in g[i]:
			e[0]+=h[i]-h[e[2]]
	for s in range(n):
		Q=[]
		heapq.heappush(Q,[0,s,s])
		while Q:
			e = heapq.heappop(Q)
			if prev[s][e[2]]!=-2: continue
			prev[s][e[2]] = e[1]
			for f in g[e[2]]:
				if e[0]<INF and f[0]<INF and dist[s][f[2]] > e[0] + f[0]:
					dist[s][f[2]] = e[0] + f[0]
					heapq.heappush(Q,[(e[0] + f[0]),f[1],f[2]])
		for u in range(n):
			if dist[s][u]<INF: dist[s][u] += h[u] - h[s]
	return True

V,E=map(int,raw_input().split())
g=[[] for i in range(V+1)]
dist=[[INF]*V for i in range(V)]
prev=[[-2]*V for i in range(V)]
for i in range(V): g[i].append([0,i,i])
for i in range(V): g[V].append([0,V,i])
for i in range(E):
	s,t,e=map(int,raw_input().split())
	g[s].append([e,s,t])
if not shortestPath(g,dist,prev):
	print("NEGATIVE CYCLE")
else:
	for i in range(V):
		print(' '.join("INF" if dist[i][j]>=INF else str(dist[i][j]) for j in range(V)))

Solution (Python):

import sys,heapq
if 'pypy' in sys.version.lower():
	import rpython.rlib.streamio
	stream=rpython.rlib.streamio.fdopen_as_stream(sys.stdin.fileno(),'r')
	raw_input=stream.readline
	def cmp_lt(x,y): return x < y
	heapq.cmp_lt=cmp_lt
elif sys.version_info[0]>=3: raw_input=input

INF=1234567890123456789
COMPILE=123456789012
def compile(a,b,c):
	return ((a+COMPILE)<<18) | (b<<9) | c
def decompile(a):
	return ((a>>18)-COMPILE,(a>>9)&511,a&511)

def shortestPath(g,dist,prev):
	n = len(g)-1
	h = [INF]*n+[0]
	for k in range(n+1):
		for i in range(n+1):
			for e in g[i]:
				if h[e[1]]<INF and e[0]<INF and h[e[2]] > h[e[1]] + e[0]:
					h[e[2]] = h[e[1]] + e[0]
					if k==n: return False 
	for i in range(n):
		for e in g[i]:
			e[0]+=h[i]-h[e[2]]
	for s in range(n):
		Q=[]
		heapq.heappush(Q,compile(0,s,s))
		while Q:
			e = decompile(heapq.heappop(Q))
			if prev[s][e[2]]!=-2: continue
			prev[s][e[2]] = e[1]
			for f in g[e[2]]:
				if e[0]<INF and f[0]<INF and dist[s][f[2]] > e[0] + f[0]:
					dist[s][f[2]] = e[0] + f[0]
					heapq.heappush(Q,compile(e[0]+f[0],f[1],f[2]))
		for u in range(n):
			if dist[s][u]<INF: dist[s][u] += h[u] - h[s]
	return True

def entry_point(argv):
	V,E=[int(e) for e in raw_input().rstrip().split(' ')]
	g=[[] for i in range(V+1)]
	dist=[[INF]*V for i in range(V)]
	prev=[[-2]*V for i in range(V)]
	for i in range(V): g[i].append([0,i,i])
	for i in range(V): g[V].append([0,V,i])
	for i in range(E):
		s,t,e=[int(e) for e in raw_input().rstrip().split(' ')]
		g[s].append([e,s,t])
	if not shortestPath(g,dist,prev):
		print("NEGATIVE CYCLE")
	else:
		for i in range(V):
			print(' '.join(["INF" if dist[i][j]>=INF else str(dist[i][j]) for j in range(V)]))
	return 0

def target(*args):
	return entry_point, None

if __name__ == '__main__': entry_point([])

Solution (Python):

import sys,heapq
if 'pypy' in sys.version.lower():
	import rpython.rlib.streamio
	stream=rpython.rlib.streamio.fdopen_as_stream(sys.stdin.fileno(),'r')
	raw_input=stream.readline
	def cmp_lt(x,y): return x < y
	heapq.cmp_lt=cmp_lt
elif sys.version_info[0]>=3: raw_input=input

INF=1234567890123456789
COMPILE=123456789012
def compile(a,b,c):
	return ((a+COMPILE)<<18) | (b<<9) | c
def decompile(a):
	return ((a>>18)-COMPILE,(a>>9)&511,a&511)

def shortestPath(g,dist,prev):
	n = len(g)-1
	h = [INF]*n+[0]
	for k in range(n+1):
		for i in range(n+1):
			for e in g[i]:
				if h[e[1]]<INF and e[0]<INF and h[e[2]] > h[e[1]] + e[0]:
					h[e[2]] = h[e[1]] + e[0]
					if k==n: return False 
	for i in range(n):
		for e in g[i]:
			e[0]+=h[i]-h[e[2]]
	for s in range(n):
		Q=[]
		heapq.heappush(Q,compile(0,s,s))
		while Q:
			e = decompile(heapq.heappop(Q))
			if prev[s][e[2]]!=-2: continue
			prev[s][e[2]] = e[1]
			for f in g[e[2]]:
				if e[0]<INF and f[0]<INF and dist[s][f[2]] > e[0] + f[0]:
					dist[s][f[2]] = e[0] + f[0]
					heapq.heappush(Q,compile(e[0]+f[0],f[1],f[2]))
		for u in range(n):
			if dist[s][u]<INF: dist[s][u] += h[u] - h[s]
	return True

def entry_point(argv):
	V,E=[int(e) for e in raw_input().rstrip().split(' ')]
	g=[[] for i in range(V+1)]
	dist=[[INF]*V for i in range(V)]
	prev=[[-2]*V for i in range(V)]
	for i in range(V): g[i].append([0,i,i])
	for i in range(V): g[V].append([0,V,i])
	for i in range(E):
		s,t,e=[int(e) for e in raw_input().rstrip().split(' ')]
		g[s].append([e,s,t])
	if not shortestPath(g,dist,prev):
		print("NEGATIVE CYCLE")
	else:
		for i in range(V):
			print(' '.join(["INF" if dist[i][j]>=INF else str(dist[i][j]) for j in range(V)]))
	return 0

def target(*args):
	return entry_point, None

if __name__ == '__main__': entry_point([])

Solution (Python):

import sys,heapq
if 'pypy' in sys.version.lower():
	import rpython.rlib.streamio
	stream=rpython.rlib.streamio.fdopen_as_stream(sys.stdin.fileno(),'r')
	raw_input=stream.readline
	def cmp_lt(x,y): return x < y
	heapq.cmp_lt=cmp_lt
	COMPILE=123456789012
	def compile(a,b,c):
		return ((a+COMPILE)<<18) | (b<<9) | c
	def decompile(a):
		return ((a>>18)-COMPILE,(a>>9)&511,a&511)
else:
	def compile(a,b,c):
		return (a,b,c)
	def decompile(a):
		return a
	if sys.version_info[0]>=3: raw_input=input

INF=1234567890123456789
def shortestPath(g,dist,prev):
	n = len(g)-1
	h = [INF]*n+[0]
	for k in range(n+1):
		for i in range(n+1):
			for e in g[i]:
				if h[e[1]]<INF and e[0]<INF and h[e[2]] > h[e[1]] + e[0]:
					h[e[2]] = h[e[1]] + e[0]
					if k==n: return False 
	for i in range(n):
		for e in g[i]:
			e[0]+=h[i]-h[e[2]]
	for s in range(n):
		Q=[]
		heapq.heappush(Q,compile(0,s,s))
		while Q:
			e = decompile(heapq.heappop(Q))
			if prev[s][e[2]]!=-2: continue
			prev[s][e[2]] = e[1]
			for f in g[e[2]]:
				if e[0]<INF and f[0]<INF and dist[s][f[2]] > e[0] + f[0]:
					dist[s][f[2]] = e[0] + f[0]
					heapq.heappush(Q,compile(e[0]+f[0],f[1],f[2]))
		for u in range(n):
			if dist[s][u]<INF: dist[s][u] += h[u] - h[s]
	return True

def entry_point(argv):
	V,E=[int(e) for e in raw_input().rstrip().split(' ')]
	g=[[] for i in range(V+1)]
	dist=[[INF]*V for i in range(V)]
	prev=[[-2]*V for i in range(V)]
	for i in range(V): g[i].append([0,i,i])
	for i in range(V): g[V].append([0,V,i])
	for i in range(E):
		s,t,e=[int(e) for e in raw_input().rstrip().split(' ')]
		g[s].append([e,s,t])
	if not shortestPath(g,dist,prev):
		print("NEGATIVE CYCLE")
	else:
		for i in range(V):
			print(' '.join(["INF" if dist[i][j]>=INF else str(dist[i][j]) for j in range(V)]))
	return 0

def target(*args):
	return entry_point, None

if __name__ == '__main__': entry_point([])

Solution (Python):

import sys,heapq
if 'pypy' in sys.version.lower():
	import rpython.rlib.streamio
	stream=rpython.rlib.streamio.fdopen_as_stream(sys.stdin.fileno(),'r')
	raw_input=stream.readline
	def cmp_lt(x,y): return x < y
	heapq.cmp_lt=cmp_lt
	COMPILE=123456789012
	def compile(a,b,c):
		return ((a+COMPILE)<<18) | (b<<9) | c
	def decompile(a):
		return ((a>>18)-COMPILE,(a>>9)&511,a&511)
else:
	def compile(a,b,c):
		return (a,b,c)
	def decompile(a):
		return a
	if sys.version_info[0]>=3: raw_input=input

INF=1234567890123456789
def shortestPath(g,dist,prev):
	n = len(g)-1
	h = [INF]*n+[0]
	for k in range(n+1):
		for i in range(n+1):
			for e in g[i]:
				if h[e[1]]<INF and e[0]<INF and h[e[2]] > h[e[1]] + e[0]:
					h[e[2]] = h[e[1]] + e[0]
					if k==n: return False 
	for i in range(n):
		for e in g[i]:
			e[0]+=h[i]-h[e[2]]
	for s in range(n):
		Q=[]
		heapq.heappush(Q,compile(0,s,s))
		while Q:
			e = decompile(heapq.heappop(Q))
			if prev[s][e[2]]!=-2: continue
			prev[s][e[2]] = e[1]
			for f in g[e[2]]:
				if e[0]<INF and f[0]<INF and dist[s][f[2]] > e[0] + f[0]:
					dist[s][f[2]] = e[0] + f[0]
					heapq.heappush(Q,compile(e[0]+f[0],f[1],f[2]))
		for u in range(n):
			if dist[s][u]<INF: dist[s][u] += h[u] - h[s]
	return True

def entry_point(argv):
	V,E=[int(e) for e in raw_input().rstrip().split(' ')]
	g=[[] for i in range(V+1)]
	dist=[[INF]*V for i in range(V)]
	prev=[[-2]*V for i in range(V)]
	for i in range(V): g[i].append([0,i,i])
	for i in range(V): g[V].append([0,V,i])
	for i in range(E):
		s,t,e=[int(e) for e in raw_input().rstrip().split(' ')]
		g[s].append([e,s,t])
	if not shortestPath(g,dist,prev):
		print("NEGATIVE CYCLE")
	else:
		for i in range(V):
			print(' '.join(["INF" if dist[i][j]>=INF else str(dist[i][j]) for j in range(V)]))
	return 0

def target(*args):
	return entry_point, None

if __name__ == '__main__': entry_point([])

Solution (Python):

import sys,heapq
if 'pypy' in sys.version.lower():
	import rpython.rlib.streamio
	stream=rpython.rlib.streamio.fdopen_as_stream(sys.stdin.fileno(),'r')
	raw_input=stream.readline
	def cmp_lt(x,y): return x < y
	heapq.cmp_lt=cmp_lt
	COMPILE=123456789012
	def compile(a,b,c):
		return ((a+COMPILE)<<18) | (b<<9) | c
	def decompile(a):
		return ((a>>18)-COMPILE,(a>>9)&511,a&511)
else:
	def compile(a,b,c):
		return (a,b,c)
	def decompile(a):
		return a
	if sys.version_info[0]>=3: raw_input=input

INF=1234567890123456789
def shortestPath(g,dist,prev):
	n = len(g)-1
	h = [INF]*n+[0]
	for k in range(n+1):
		for i in range(n+1):
			for e in g[i]:
				if h[e[1]]<INF and e[0]<INF and h[e[2]] > h[e[1]] + e[0]:
					h[e[2]] = h[e[1]] + e[0]
					if k==n: return False 
	for i in range(n):
		for e in g[i]:
			e[0]+=h[i]-h[e[2]]
	for s in range(n):
		Q=[]
		heapq.heappush(Q,compile(0,s,s))
		while Q:
			e = decompile(heapq.heappop(Q))
			if prev[s][e[2]]!=-2: continue
			prev[s][e[2]] = e[1]
			for f in g[e[2]]:
				if e[0]<INF and f[0]<INF and dist[s][f[2]] > e[0] + f[0]:
					dist[s][f[2]] = e[0] + f[0]
					heapq.heappush(Q,compile(e[0]+f[0],f[1],f[2]))
		for u in range(n):
			if dist[s][u]<INF: dist[s][u] += h[u] - h[s]
	return True

def entry_point(argv):
	V,E=[int(e) for e in raw_input().rstrip().split(' ')]
	g=[[] for i in range(V+1)]
	dist=[[INF]*V for i in range(V)]
	prev=[[-2]*V for i in range(V)]
	for i in range(V): g[i].append([0,i,i])
	for i in range(V): g[V].append([0,V,i])
	for i in range(E):
		s,t,e=[int(e) for e in raw_input().rstrip().split(' ')]
		g[s].append([e,s,t])
	if not shortestPath(g,dist,prev):
		print("NEGATIVE CYCLE")
	else:
		for i in range(V):
			print(' '.join(["INF" if dist[i][j]>=INF else str(dist[i][j]) for j in range(V)]))
	return 0

def target(*args):
	return entry_point, None

if __name__ == '__main__': entry_point([])

Solution (Python):

import sys,heapq
try:
	import rpython.rlib.streamio
	stream=rpython.rlib.streamio.fdopen_as_stream(sys.stdin.fileno(),'r')
	raw_input=stream.readline
	def cmp_lt(x,y): return x < y
	heapq.cmp_lt=cmp_lt
	COMPILE=123456789012
	def compile(a,b,c):
		return ((a+COMPILE)<<18) | (b<<9) | c
	def decompile(a):
		return ((a>>18)-COMPILE,(a>>9)&511,a&511)
except ImportError:
	def compile(a,b,c):
		return (a,b,c)
	def decompile(a):
		return a
	if sys.version_info[0]>=3: raw_input=input

INF=1234567890123456789
def shortestPath(g,dist,prev):
	n = len(g)-1
	h = [INF]*n+[0]
	for k in range(n+1):
		for i in range(n+1):
			for e in g[i]:
				if h[e[1]]<INF and e[0]<INF and h[e[2]] > h[e[1]] + e[0]:
					h[e[2]] = h[e[1]] + e[0]
					if k==n: return False 
	for i in range(n):
		for e in g[i]:
			e[0]+=h[i]-h[e[2]]
	for s in range(n):
		Q=[]
		heapq.heappush(Q,compile(0,s,s))
		while Q:
			e = decompile(heapq.heappop(Q))
			if prev[s][e[2]]!=-2: continue
			prev[s][e[2]] = e[1]
			for f in g[e[2]]:
				if e[0]<INF and f[0]<INF and dist[s][f[2]] > e[0] + f[0]:
					dist[s][f[2]] = e[0] + f[0]
					heapq.heappush(Q,compile(e[0]+f[0],f[1],f[2]))
		for u in range(n):
			if dist[s][u]<INF: dist[s][u] += h[u] - h[s]
	return True

def entry_point(argv):
	V,E=[int(e) for e in raw_input().rstrip().split(' ')]
	g=[[] for i in range(V+1)]
	dist=[[INF]*V for i in range(V)]
	prev=[[-2]*V for i in range(V)]
	for i in range(V): g[i].append([0,i,i])
	for i in range(V): g[V].append([0,V,i])
	for i in range(E):
		s,t,e=[int(e) for e in raw_input().rstrip().split(' ')]
		g[s].append([e,s,t])
	if not shortestPath(g,dist,prev):
		print("NEGATIVE CYCLE")
	else:
		for i in range(V):
			print(' '.join(["INF" if dist[i][j]>=INF else str(dist[i][j]) for j in range(V)]))
	return 0

def target(*args):
	return entry_point, None

if __name__ == '__main__': entry_point([])

Solution (Python):

import sys,heapq
try:
	import rpython.rlib.streamio
	stream=rpython.rlib.streamio.fdopen_as_stream(sys.stdin.fileno(),'r')
	raw_input=stream.readline
	def cmp_lt(x,y): return x < y
	heapq.cmp_lt=cmp_lt
	COMPILE=123456789012
	def compile(a,b,c):
		return ((a+COMPILE)<<18) | (b<<9) | c
	def decompile(a):
		return ((a>>18)-COMPILE,(a>>9)&511,a&511)
except ImportError:
	def compile(a,b,c):
		return (a,b,c)
	def decompile(a):
		return a
	if sys.version_info[0]>=3: raw_input=input

INF=1234567890123456789
def shortestPath(g,dist,prev):
	n = len(g)-1
	h = [INF]*n+[0]
	for k in range(n+1):
		for i in range(n+1):
			for e in g[i]:
				if h[e[1]]<INF and e[0]<INF and h[e[2]] > h[e[1]] + e[0]:
					h[e[2]] = h[e[1]] + e[0]
					if k==n: return False 
	for i in range(n):
		for e in g[i]:
			e[0]+=h[i]-h[e[2]]
	for s in range(n):
		Q=[]
		heapq.heappush(Q,compile(0,s,s))
		while Q:
			e = decompile(heapq.heappop(Q))
			if prev[s][e[2]]!=-2: continue
			prev[s][e[2]] = e[1]
			for f in g[e[2]]:
				if e[0]<INF and f[0]<INF and dist[s][f[2]] > e[0] + f[0]:
					dist[s][f[2]] = e[0] + f[0]
					heapq.heappush(Q,compile(e[0]+f[0],f[1],f[2]))
		for u in range(n):
			if dist[s][u]<INF: dist[s][u] += h[u] - h[s]
	return True

def entry_point(argv):
	V,E=[int(e) for e in raw_input().rstrip().split(' ')]
	g=[[] for i in range(V+1)]
	dist=[[INF]*V for i in range(V)]
	prev=[[-2]*V for i in range(V)]
	for i in range(V): g[i].append([0,i,i])
	for i in range(V): g[V].append([0,V,i])
	for i in range(E):
		s,t,e=[int(e) for e in raw_input().rstrip().split(' ')]
		g[s].append([e,s,t])
	if not shortestPath(g,dist,prev):
		print("NEGATIVE CYCLE")
	else:
		for i in range(V):
			print(' '.join(["INF" if dist[i][j]>=INF else str(dist[i][j]) for j in range(V)]))
	return 0

def target(*args):
	return entry_point, None

if __name__ == '__main__': entry_point([])

Solution (Python):
INF = 1e12

v, e = (int(s) for s in input().split())
cost = [[INF] * v for i in range(v)]
for i in range(v):
    cost[i][i] = 0

for i in range(e):
    si, ti, di = (int(s) for s in input().split())
    cost[si][ti] = di

for k in range(v):
    for i in range(v):
        for j in range(v):
            if cost[i][k] != INF and cost[k][j] != INF:
                if cost[i][j] > cost[i][k] + cost[k][j]:
                    cost[i][j] = cost[i][k] + cost[k][j]

if any(cost[i][i] for i in range(v)):
    print('NEGATIVE CYCLE')
else:
    for di in cost:
        ldi = []
        for dij in di:
            if dij == INF:
                ldi.append('INF')
            else:
                ldi.append(str(dij))
        print(' '.join(ldi))

Solution (Python):
INF = 1e12

v, e = map(int, input().split())
cost = [[INF] * v for i in range(v)]
for i in range(v):
    cost[i][i] = 0

for i in range(e):
    si, ti, di = map(int, input().split())
    cost[si][ti] = di

for k in range(v):
    for i in range(v):
        for j in range(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] for i in range(v)):
    print('NEGATIVE CYCLE')
else:
    for di in cost:
        ldi = []
        for dij in di:
            if dij == INF:
                ldi.append('INF')
            else:
                ldi.append(str(dij))
        print(' '.join(ldi))

Solution (Python):

import sys,heapq
try:
	import rpython.rlib.streamio
	stream=rpython.rlib.streamio.fdopen_as_stream(sys.stdin.fileno(),'r')
	raw_input=stream.readline
	def cmp_lt(x,y): return x < y
	heapq.cmp_lt=cmp_lt
	COMPILE=123456789012
	def compile(a,b,c):
		return ((a+COMPILE)<<18) | (b<<9) | c
	def decompile(a):
		return ((a>>18)-COMPILE,(a>>9)&511,a&511)
except ImportError:
	def compile(a,b,c):
		return (a,b,c)
	def decompile(a):
		return a
	if sys.version_info[0]>=3: raw_input=input

INF=1234567890123456789
def shortestPath(g,dist,prev):
	n = len(g)-1
	h = [INF]*n+[0]
	for k in range(n+1):
		for i in range(n+1):
			for e in g[i]:
				if h[e[1]]<INF and e[0]<INF and h[e[2]] > h[e[1]] + e[0]:
					h[e[2]] = h[e[1]] + e[0]
					if k==n: return False 
	for i in range(n):
		for e in g[i]:
			e[0]+=h[i]-h[e[2]]
	for s in range(n):
		Q=[]
		heapq.heappush(Q,compile(0,s,s))
		while Q:
			e = decompile(heapq.heappop(Q))
			if prev[s][e[2]]!=-2: continue
			prev[s][e[2]] = e[1]
			for f in g[e[2]]:
				if e[0]<INF and f[0]<INF and dist[s][f[2]] > e[0] + f[0]:
					dist[s][f[2]] = e[0] + f[0]
					heapq.heappush(Q,compile(e[0]+f[0],f[1],f[2]))
		for u in range(n):
			if dist[s][u]<INF: dist[s][u] += h[u] - h[s]
	return True

def entry_point(argv):
	V,E=[int(e) for e in raw_input().rstrip().split(' ')]
	g=[[] for i in range(V+1)]
	dist=[[INF]*V for i in range(V)]
	prev=[[-2]*V for i in range(V)]
	for i in range(V): g[i].append([0,i,i])
	for i in range(V): g[V].append([0,V,i])
	for i in range(E):
		s,t,e=[int(e) for e in raw_input().rstrip().split(' ')]
		g[s].append([e,s,t])
	if not shortestPath(g,dist,prev):
		print("NEGATIVE CYCLE")
	else:
		for i in range(V):
			print(' '.join(["INF" if dist[i][j]>=INF else str(dist[i][j]) for j in range(V)]))
	return 0

def target(*args):
	return entry_point

if __name__ == '__main__': entry_point([])

Solution (Python):
import sys
from heapq import heappush, heappop


def floyd(dis, V):
    for i in range(V): dis[i][i] = 0
    
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dis[i][k] != sys.maxint and dis[k][j] != sys.maxint and dis[i][k] + dis[k][j] < dis[i][j]:
                    dis[i][j] = dis[i][k] + dis[k][j]
                    
    for i in range(V):
        if dis[i][i] < 0:
            return 'NEGATIVE CYCLE'
    return 'NO NEGATIVE CYCLE'
    
    
if __name__ == '__main__':
    line = sys.stdin.readline()
    V, E = line.split()
    V, E = int(V), int(E)
    dis = [[sys.maxint for j in range(V)] for i in range(V)]
    
    for i in range(E):
        line = sys.stdin.readline()
        a, b, w = line.split()
        a, b, w = int(a), int(b), int(w)
        dis[a][b] = w
        
        
    judge = floyd(dis, V)
    if judge == 'NEGATIVE CYCLE':
        sys.stdout.write(judge + '\n')
    else:
        for i in range(V):
            sys.stdout.write(' '.join(map(lambda x: str(x) if x < sys.maxint else 'INF', dis[i])) + '\n')