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
inf=float("inf")  

icase=0
if icase==0:
    nv,ne=map(int,input().split())
    dp=[[inf]*nv for i in range(nv)] 

    for i in range(ne):
        si,ti,di=map(int,input().split())
        dp[si][ti]=di
elif icase==1:
    nv,ne=4,6
    dp=[[inf,1,5,inf], [inf,inf,2,4], [inf,inf,inf,1], [inf,inf,7,inf]]    
elif icase==2:
    nv,ne=4,6
    dp=[[inf,1,-5,inf], [inf,inf,2,4], [inf,inf,inf,1], [inf,inf,7,inf]]    
elif icase==3:
    nv,ne=4,6
    dp=[[inf,1,5,inf], [inf,inf,2,4], [inf,inf,inf,1], [inf,inf,-7,inf]]
for i in range(nv):
    dp[i][i]=0

for k in range(nv):
    for i in range(nv):
        for j in range(nv):
            dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])


for i in range(nv):
    if dp[i][i]<0:
        print("NEGATIVE CYCLE")
        sys.exit()
for i in range(nv):
    for j in range(nv):
        if dp[i][j]==inf:
            dp[i][j]="INF"
for i in range(nv):
    for j in range(nv-1):
        print(dp[i][j],end=" ")
    print(dp[i][nv-1])

Solution (Python):
V, E = map(int, input().split())

dists = [[float('inf')]*V for _ in range(V)]

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

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

for k in range(V):
    for i in range(V):
        for j in range(V):
            dists[i][j] = min(dists[i][j], dists[i][k]+dists[k][j])
            if i == j and dists[i][j] < 0:
                print('NEGATIVE CYCLE')
                exit()

for row in dists:
    print(' '.join(['INF' if d == float('inf') else str(d) for d in row]))

Solution (Python):
def warshall_floyd():
    for k in range(n):
        for i in range(n):
            for j in range(n):
                A[i][j] = min(A[i][j],A[i][k]+A[k][j])
    return

V,E = map(int,input().split())
n = V
A = [[float('inf')]*V for _ in range(n)]
for i in range(E):
    s,t,d = map(int,input().split())
    A[s][t] = d
for i in range(n):
    A[i][i] = 0
    
warshall_floyd()

negative_flag = False
for i in range(n):
    if A[i][i]<0:
        negative_flag = True
        
for i in range(n):
    for j in range(n):
        if A[i][j] == float("inf"):
            A[i][j] = 'INF'
        
if negative_flag:
    print("NEGATIVE CYCLE")
else:
    for i in range(n):
        print(' '.join(map(str,A[i])))

Solution (Python):
def warshall_floyd():
    inf=float("inf")
    v,e=map(int,input().split())
    
    dp=[[[inf]*v for i in range(v)] for j in range(v+1)]

    
    for i in range(v):
        dp[0][i][i]=0
    for _ in range(e):
        s,t,d=map(int,input().split())
        dp[0][s][t]=d
    
    for i in range(1,v+1):
        for j in range(v):
            for k in range(v):
                dp[i][j][k]=min(dp[i-1][j][k],dp[i-1][j][i-1]+dp[i-1][i-1][k])
    
    
    for i in range(v):
        if dp[v][i][i]<0 :
            print("NEGATIVE CYCLE")
            return None
    
    for i in range(v):
        print(" ".join(["INF" if x ==inf else str(x) for x in dp[v][i]]))

warshall_floyd()

Solution (Python):
def warshall_floyd(d):
    
    for k in range(v):
        for i in range(v):
            for j in range(v):
                if d[i][k]!=float('inf') and d[k][j]!=float('inf'):
                    d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

v,e = map(int,input().split())
d = [[float('inf')]*v for i in range(v)] 
for i in range(e):
    x,y,z = map(int,input().split())
    d[x][y] = z
for i in range(v):
    d[i][i] = 0 
d=warshall_floyd(d)
for i in range(v):
    if d[i][i]<0:
        print('NEGATIVE CYCLE')
        exit()
ans=[['']*v for _ in range(v)]
for i in range(v):
    for j in range(v):
        if d[i][j]==float('inf'):
            ans[i][j]='INF'
        else:
            ans[i][j]=str(d[i][j])
for i in range(v):
    print(*ans[i],sep=' ')

Solution (Python):
def floyd_warshall(dp, V):
    for k in range(V):
        for i in range(V):
            for j in range(V):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

    
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dp[i][k] + dp[k][j] < dp[i][j]:
                    return -1
    return dp

INF = float('inf')
V, E = [int(x) for x in input().split()]
dp = [[INF for _ in range(V)] for _ in range(V)]
for i in range(V):
    dp[i][i] = 0

for j in range(E):
    s, t, d = [int(x) for x in input().split()]
    dp[s][t] = d

dp = floyd_warshall(dp, V)
if dp == -1:
    print("NEGATIVE CYCLE")
else:
    for i in range(V):
        for j in range(V):
            if dp[i][j] == INF:
                dp[i][j] = "INF"
        print(*dp[i])

Solution (Python):

INF = float('inf')

V, E = list(map(int, input().split()))

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

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

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

has_negative_cycle = False
for i in range(V):
    for j in range(V):
        if i == j and D[i][j] < 0:
            has_negative_cycle = True
        if D[i][j] == INF:
            D[i][j] = 'INF'
        else:
            D[i][j] = str(D[i][j])


if has_negative_cycle:
    print('NEGATIVE CYCLE')
else:
    for row in D:
        print(' '.join(row))

Solution (Python):
vn,en = map(int,input().split())
dis = [[float("inf") for __ in range(vn)] for _ in range(vn)]
for i in range(vn):
    dis[i][i] = 0
for _ in range(en):
    s,t,d = map(int,input().split())
    dis[s][t] = d
for k in range(vn):
    for i in range(vn):
        for j in range(vn):
            dis[i][j] = min(dis[i][k]+dis[k][j], dis[i][j])
            if i==j:
                if dis[i][j]<0:
                    print('NEGATIVE CYCLE')
                    exit()
for i in range(vn):
    ans = []
    for j in range(vn):
        if dis[i][j] == float('inf'):
            ans.append('INF')
        else:
            ans.append(str(dis[i][j]))
    print(' '.join(ans))

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    N, M = map(int, input().split())
    INF = float('inf')
    D = [[INF]*N for _ in [0]*N]
    for _ in [0]*M:
        a, b, c = map(int, input().split())
        D[a][b] = c

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

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

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

    for d in D:
        print(' '.join(map(lambda x: str(x) if x < INF else 'INF', d)))


if __name__ == '__main__':
    main()

Solution (Python):
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

INF = float('inf')

v,e = mi()
dp = [[float('inf') for i in range(v)] for j in range(v)]

path = [[] for i in range(v)]
for i in range(e):
    s,t,d = mi()
    path[s].append((t,d))
    dp[s][t] = d

for i in range(v):
    dp[i][i] = 0


for k in range(v):
    for i in range(v):
        for j in range(v):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])



for i in range(v):
    if dp[i][i] < 0:
        print('NEGATIVE CYCLE')
        break
else:
    for i in range(v):
        for j in range(v):
            c = dp[i][j]
            if c == INF:
                c = 'INF'
            if j != v-1:
                print(c,end=" ")
            else:
                print(c)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    V, E = map(int, input().split())
    cost = [[f_inf] * V for _ in range(V)]
    for i in range(V):
        cost[i][i] = 0
    for _ in range(E):
        s, t, d = map(int, input().split())
        cost[s][t] = d

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

    for i in range(V):
        for j in range(V):
            if i == j and cost[i][j] < 0:
                print("NEGATIVE CYCLE")
                exit()
            if cost[i][j] == f_inf:
                cost[i][j] = "INF"

    for res in cost:
        print(*res)


if __name__ == '__main__':
    resolve()

Solution (Python):
def main():
    V, E = map(int, input().split())
    G = [[float("INF")] * V for _ in range(V)]
    for i in range(V):
        G[i][i] = 0
    for _ in range(E):
        s, t, d = map(int, input().split())
        G[s][t] = d

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

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

        for j in range(V):
            if G[i][j] == float("INF"):
                G[i][j] = "INF"
    for g in G:
        print(*g)


if __name__ == '__main__':
    main()

Solution (Python):
V,E = map(int,input().split())
matrix = [ [float('inf')]*V for _ in range(V) ]

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

for _ in range(E):
  u,v,w = map(int,input().split())
  matrix[u][v] = w

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

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


for i in range(V):
  print(" ".join(map(str, [ "INF" if e==float('inf') else e for e in matrix[i] ])))

Solution (Python):
V, E = map(int, input().split())
inf = float('inf')
dps = [[inf for _ in range(V)] for _ in range(V)]

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


for i in range(V):
    dps[i][i] = 0
for v in range(V):
    for i in range(V):
        for j in range(V):
            dps[i][j] = min(dps[i][j], dps[i][v] + dps[v][j])

flag = False
for i in range(V):
    if dps[i][i] < 0:
        flag = True
if flag:
    print('NEGATIVE CYCLE')
else:
    for dp in dps:
        print(*['INF' if num == inf else num for num in dp])

Solution (Python):
n,m=map(int,input().split())
INF=10**18
dis=[[INF for _ in range(n)]for _ in range(n)]
for i in range(m):
  a,b,c=map(int,input().split())
  dis[a][b]=c
for i in range(n):
  dis[i][i]=0
for k in range(n):
  for i in range(n):
    for j in range(n):
      dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j])
for i in range(n):
  for j in range(n):
    if dis[i][j]>=10**10:dis[i][j]='INF'
  if dis[i][i]<0:
    print('NEGATIVE CYCLE')
    exit()
for i in dis:
  print(*i)

Solution (Python):
import sys
import bisect
import math
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from operator import itemgetter
inf=10**20
v,e=map(int,readline().split())

d=[[inf for j in range(v)] for i in range(v)]
for i in range(v):
    d[i][i]=0
for i in range(e):
    a,b,c=map(int,readline().split())
    d[a][b]=c

for k in range(v):
    for i in range(v):
        for j in range(v):
            d[i][j]=min(d[i][j],d[i][k]+d[k][j])
ng=0
for i in range(v):
    if d[i][i]<0:
        ng=1
        break


if ng:
    print("NEGATIVE CYCLE")
else:
    for i in range(v):
        ans=""
        for j in range(v):
            if d[i][j]>2e9:
                ans+="INF"+" "
            else:
                ans+=str(d[i][j])+" "
        print(ans.rstrip())

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
	V,E = map(int,input().split())
	dist = [[INF]*V for _ in range(V)]
	for _ in range(E):
		s,t,d = map(int,input().split())
		dist[s][t] = d
	
	for k in range(V):
		for i in range(V):
			for j in range(V):
				if dist[i][k] != INF and dist[k][j] != INF and 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:
			print('NEGATIVE CYCLE')
			return
		dist[i][i] = 0
	
	for i in range(V):
		print(' '.join(map(lambda x:'INF' if x == INF else str(x),dist[i])))
if __name__ == '__main__':
	main()

Solution (Python):
V,E = list(map(int,input().split()))
STD = [list(map(int,input().split())) for _ in range(E)]

D = [[float('inf')]*V for _ in range(V)]

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

for std in STD:
    D[std[0]][std[1]] = std[2]

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

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

for d in D:
    print(*list(map(lambda x: str(x) if x != float('inf') else 'INF', d)))

Solution (Python):
from math import isinf

V, E = map(int, input().split())
d = [[float('inf') for i in range(V)] for j in range(V)]

for i in range(V):
    d[i][i] = 0
    
for i in range(E):
    s, t, w = map(int,input().split())
    d[s][t] = w
    
for k in range(V):
    for j in range(V):
        for i 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')
        exit()

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

Solution (Python):


v, e = map(int, input().split())
dp = [[[float("Inf")] * (v) for x in range(v)] for y in range(v+1)]

for i in range(e):
    s, t, d = map(int, input().split())
    dp[0][s][t] = d

for i in range(v):
    dp[0][i][i] = 0

for k in range(v):
    for i in range(v):
        for j in range(v):
            dp[k+1][i][j] = min(dp[k][i][j], dp[k][i][k] + dp[k][k][j])

for i in range(v):
    if dp[v][i][i] < 0:
        print("NEGATIVE CYCLE")
        break
else:
    for i in range(v):
        print(*[(str(x)).upper() for x in dp[v][i]])

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]

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

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


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

ans = []
for i in range(V):
    tmp = []
    for j in range(V):
        if C[i][j] == float('inf'):
            tmp.append('INF')
        else:
            tmp.append(C[i][j])
    ans.append(tmp)

for i in range(V):
    print(*(ans[i]))

Solution (Python):
v,e=map(int,input().split())
dis=[[10**15 for _ in range(v)]for _ in range(v)]
for i in range(e):
	a,b,c=map(int,input().split())
	dis[a][b]=c
for i in range(v):
	dis[i][i]=0
for k in range(v):
	for i in range(v):
		for j in range(v):
			dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j])
for i in range(v):
	if dis[i][i]<0:
		print("NEGATIVE CYCLE")
		exit()
for i in range(v):
	ans=[]
	for j in range(v):
		if dis[i][j]>=10**14:
			ans.append("INF")
		else:
			ans.append(dis[i][j])
	print(*ans)

Solution (Python):
import sys
import itertools

import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

v, e = map(int, input().split())
INF = float("inf")
dist = [[INF for _ in range(v)] for _ in range(v)]
for i in range(e):
    s, t, d = map(int, input().split())
    dist[s][t] = d

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


has_negative = False
for k in range(v):
    for i in range(v):
        for j in range(v):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                has_negative = True
                break
if has_negative:
    print("NEGATIVE CYCLE")
    exit()

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

Solution (Python):
INF = 2**120

import copy
import sys

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

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

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

d1 = copy.deepcopy(d)

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

for i in range(V):
    for j in range(V):
        if d[i][j] != d1[i][j]:
            print('NEGATIVE CYCLE')
            sys.exit()

for i in range(V):
    for j in range(V):
        if d[i][j] > 2**60:
            d[i][j] = 'INF'

for i in range(V):
    print(' '.join([str(j) for j in d[i]]))

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

def floyd_warshall(dist):                                               
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]                
                                                                        
    return dist


V, E = map(int, input().split())                                        

INF = float("inf")

dist = [[INF] * V for _ in range(V)]                           
for _ in range(E):
    i,j,weight = map(int,input().split())
    
    
    dist[i][j] = weight
    
for i in range(V):
    dist[i][i] = 0                                                      

d = floyd_warshall(dist)                                                

nagativity = False                                                      
for i in range(V):
    if d[i][i] < 0:
        nagativity = True
if nagativity:
    print('NEGATIVE CYCLE')
else:
    for a in d:
        print(*[x if x != INF else "INF" for x in a])

Solution (Python):
def warshallFloyd(V, dp):
    for k in range(V):
        for i in range(V):
            for j in range(V):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

V, E = map(int,input().split())
dp = [[float('inf')]*V for _ in range(V)]
for i in range(V):
    dp[i][i] = 0
for _ in range(E):
    f, t, d = map(int,input().split())
    dp[f][t] = d
warshallFloyd(V, dp)

ncircle = False
for i in range(V):
    if dp[i][i] < 0:
        ncircle = True
if ncircle:
    print('NEGATIVE CYCLE')
else:
    for d in dp:
        print(' '.join(map(str, d)).replace('inf', 'INF'))

Solution (Python):
import sys
INFTY=sys.maxsize


def readinput():
    nv,ne=list(map(int,input().split()))
    nMap=[]
    for i in range(nv):
        l=[]
        for _ in range(nv):
            l.append(INFTY)
        nMap.append(l)
        nMap[i][i]=0
    for _ in range(ne):
        s,t,d=list(map(int,input().split()))
        nMap[s][t]=d
    return nv,ne,nMap

def warshalFloyd(nv, nMap):
    for k in range(nv):
        for i in range(nv):
            if(nMap[i][k]==INFTY):
                continue
            for j in range(nv):
                if(nMap[k][j]==INFTY):
                    continue
                nMap[i][j] = min(nMap[i][j], nMap[i][k]+nMap[k][j])
    return nMap

def main(nv,ne,nMap):
    nMap=warshalFloyd(nv,nMap)
    
    isNegative=False
    for i in range(nv):
        if nMap[i][i]<0:
            isNegative=True
    if isNegative==True:
        print('NEGATIVE CYCLE')
    else:
        for i in range(nv):
            for j in range(nv):
                
                if(nMap[i][j]==INFTY):
                    print('INF',end='')
                else:
                    print(nMap[i][j], end='')
                if j==nv-1:
                    print('')
                else:
                    print(' ',end='')
                        

if __name__=='__main__':
    nv,ne,nMap=readinput()
    
    main(nv,ne,nMap)

Solution (Python):
INF=100000000000000
def warshall_floyd(D):
    for k in range(V):
        for i in range(V):
            for j in range(V):
                D[i][j]=min(D[i][j],D[i][k]+D[k][j])

if __name__ == "__main__":
    V,E=map(int,input().split())
    D=[[INF if j!=i else 0 for j in range(V)] for i in range(V)]
    dall=0

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

    warshall_floyd(D)
    flg=False

    for i in range(V):
        if D[i][i]<0:
            flg=True
            break

    
    if flg:
        print("NEGATIVE CYCLE")
    else:
        
        for i in range(V):
            print(' '.join(["INF" if j>dall else str(j) for j in D[i]]))

Solution (Python):


"""Computes all pairs shortest paths in a graph using the Warshall-Floyd algorithm.

Verification: [GRL_1_C]()
"""


import itertools



INF = 10 ** 10


def in_place_warshall_floyd(adj_matrix):
    """Solves the all-pairs shortest path problem using the Warshall-Floyd algorithm.

    The adjacency matrix A of the graph. This object must be
    able to be treated as a $n \times n$ matrix. $A_{i, j}$ represents the
    cost of the edge $i \rightarrow j$. If $A_{i, j}$ is `INF`` or more,
    there is no edge between the two vertices. For all $x$, $A_{x, x} = 0$.
    Note that this matrix will be modified in place during calculation.
    
    Returns: whether the graph has a negative cycle.
    """

    n = len(adj_matrix)
    for k, i, j in itertools.product(range(n), repeat=3):
        if adj_matrix[i][k] == INF or adj_matrix[k][j] == INF:
            continue
        adj_matrix[i][j] = min(adj_matrix[i][j],
                               adj_matrix[i][k] + adj_matrix[k][j])
    return any(adj_matrix[i][i] < 0 for i in range(n))


def dist_to_str(d):
    if d < INF:
        return str(d)
    else:
        return "INF"


def main():
    v, e = (int(z) for z in input().split())
    adj_matrix = [[INF for _ in range(v)] for _ in range(v)]
    for i in range(v):
        adj_matrix[i][i] = 0
    for _ in range(e):
        s, t, d = (int(z) for z in input().split())
        adj_matrix[s][t] = d
    has_nc = in_place_warshall_floyd(adj_matrix)
    if has_nc:
        print("NEGATIVE CYCLE")
    else:
        for line in adj_matrix:
            print(*(dist_to_str(d) for d in line))


if __name__ == '__main__':
    main()

Solution (Python):
import sys

input = sys.stdin.readline

def main():
    V, E = map(int, input().split())
    grid = [[float('inf')]*V for _ in range(V)]
    for _ in range(E):
        s, t, d = map(int, input().split())
        grid[s][t] = d
    
    for i in range(V):
        grid[i][i] = 0

    for k in range(V):
        for i in range(V):
            for j in range(V):
                grid[i][j] = min(grid[i][j], grid[i][k] + grid[k][j])
    
    for i in range(V):
        for j in range(V):
            if grid[i][j] < 0 and grid[j][i] < 0:
                print('NEGATIVE CYCLE')
                return
    
    for tmp in grid:
        ans = ['INF' if x == float('inf') else x for x in tmp ]
        print(*ans)

if __name__ == "__main__":
    main()

Solution (Python):


import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    it = map(int, sys.stdin.read().split())
    V, E = next(it), next(it)
    inf = float("inf")

    dp = [[inf for i in range(V)] for i in range(V)]

    for si, ti, di in zip(it, it, it):
        dp[si][ti] = di
    for i in range(V):
        dp[i][i] = 0

    for s in range(V):
        for t, dts in ((t, dp[t][s]) for t in range(V)):
            if s == t: continue
            for u, (dtu, dsu) in enumerate(zip(dp[t], dp[s])):

                d1 = dts + dsu
                if dtu > d1:
                    if u == t:
                        return print("NEGATIVE CYCLE")
                    dp[t][u] = d1
                    update = True

    for dr in dp:
        print(*["INF" if x == inf else x for x in dr])



if __name__ == "__main__":
    resolve()

Solution (Python):
import sys

def w_f(dp):
    for k in range(v):
        for i in range(v):
            for j in range(v):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
    
    for i in range(v):
        for j in range(v):
            if dp[i][i] < 0:
                print('NEGATIVE CYCLE')
                sys.exit()
            
            if dp[i][j] == float('inf'):
                dp[i][j] = 'INF'
    return dp

v,e = map(int, input().split())
dp = [[float('inf')]*v for _ in range(v)]
for i in range(e):
    s,t,d = map(int, input().split())
    dp[s][t] = d
    
for i in range(v):
    dp[i][i] = 0
    
res = w_f(dp)
for i in range(v):
    print(*res[i])

Solution (Python):
class NegativeWeightDirectedGraph():
    def __init__(self, V):
        self.V = V
        self.INF = 10**10
        self.G = [[self.INF]*V for _ in range(V)]
        for i in range(V):
            self.G[i][i] = 0

    def append(self, src, to, weight):
        self.G[src][to] = weight

    def warshallFloyd(self):
        for k in range(self.V):
            for i in range(self.V):
                for j in range(self.V):
                    if self.G[i][k] != self.INF and self.G[k][j] != self.INF:
                        w = self.G[i][k] + self.G[k][j]
                        self.G[i][j] = min(self.G[i][j], w)
        
        for i in range(V):
            if self.G[i][i] < 0:
                return None       
        return self.G

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

ans = G.warshallFloyd()
if ans == None:
    print "NEGATIVE CYCLE"
else:
    for ds in ans:
        print " ".join(map(lambda d: str(d) if d != G.INF else "INF", ds))

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

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

nega=0
for i in range(V):
    if dp[i][i]<0:
        nega=1
if nega:
    print("NEGATIVE CYCLE")
else:
    for i in range(V):
        if dp[i][0]==float('inf'):
            print("INF",end='')
        else:
            print(dp[i][0],end='')
        for j in range(1,V):
            if dp[i][j]==float('inf'):
                print(" INF",end='')
            else:
                print(" {}".format(dp[i][j]),end='')
        print()

Solution (Python):
from copy import deepcopy

V,E = list(map(int,input().split()))


INF = 2**36 - 1

M=[[INF]*V for x in range (V)]
for n in range(E):
    input_temp = list(map(int,input().split()))
    M[input_temp[0]][input_temp[1]]=input_temp[2]
    
for v in range(V):
    M[v][v]=0    

def warshallFloyd(M):
    ret = deepcopy(M)
    for k in range(V):
        for i in range(V):
            if ret[i][k] == INF:
                continue
            for j in range(V):
                if ret[k][j] == INF:
                    continue
                ret[i][j] = min(ret[i][j], ret[i][k] + ret[k][j])
    return ret 

def check_negative_cycle(W):
    negative_cycle=False
    for v in range(V):
        if W[v][v] < 0:
            negative_cycle=True
            break
    return negative_cycle

ans=warshallFloyd(M)
negative_cycle=check_negative_cycle(ans)

if negative_cycle:
    print('NEGATIVE CYCLE')
else:
    for i in range(V):
        for j in range(V):
            print(ans[i][j] if ans[i][j] != INF else "INF", end='')
            if j == V - 1:
                print()
            else:
                print(' ', end='')

Solution (Python):
def warshall_floyd(dp, v):
    for k in range(v):
        for i in range(v):
            for j in range(v):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])


def check(dp, v):
    for k in range(v):
        for i in range(v):
            for j in range(v):
                if dp[i][j] > dp[i][k] + dp[k][j]:
                    return False
    return True


def main():
    v, e = map(int, input().split())
    INF = 10 ** 10
    MAX = 2 * (10 ** 7)
    MIN = -2 * (10 ** 7)
    dp = [[INF for i in range(v)] for j in range(v)]
    for i in range(e):
        s, t, d = map(int, input().split())
        dp[s][t] = d
    for i in range(v):
        for j in range(v):
            if i == j:
                dp[i][j] = 0

    warshall_floyd(dp, v)
    if not check(dp, v):
        print("NEGATIVE CYCLE")
    else:
        for i in range(v):
            for j in range(v):
                if j > 0:
                    print(end=' ') 
                if dp[i][j] > MAX * v or dp[i][j] < MIN * v:
                    print("INF", end='')
                else:
                    print(dp[i][j], end='')
            print()


if __name__ == '__main__':
    main()

Solution (Python):
class WarshallFloyd:
    
    def __init__(self,n,_first_index=0):
        self.v = n
        self._first_idx=_first_index
        self.d = [[float("INF")]*(n) for _ in range(n)]
        for i in range(n):
            self.d[i][i] = 0

    def path(self,x,y,c,directed=0):
        if x == y:
            return False
        f=self._first_idx
        self.d[x-f][y-f] = c
        if directed==0:
            self.d[y-f][x-f] = c
        return True

    def build(self):
        for k in range(self.v):
            for i in range(self.v):
                for j in range(self.v):
                    self.d[i][j] = min(self.d[i][j], self.d[i][k] + self.d[k][j])
        return self.d
v,e=map(int,input().split())
w=WarshallFloyd(v)
for i in range(e):
    a,s,d=map(int,input().split())
    w.path(a,s,d,1)
d=w.build()
for i in range(v):
    if d[i][i]<0:print("NEGATIVE CYCLE");exit()
for i in d:
    for j in i[:-1]:
        print("INF"if j==float("INF") else j,end=" ")
    print(i[-1]if i[-1]!=float("INF") else "INF")