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):
v, e = map(int, input().split())

INF = 10 ** 18
d = [[INF]*v for _ in range(v)]

for i in range(e):
    frm, to, dis = map(int, input().split())
    d[frm][to] = 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])
            
neg = 0

for i in range(v):
    for j in range(v):
        if d[i][j] + d[j][i]<0:
            neg = 1
            
if neg:
    print('NEGATIVE CYCLE')
else:
    for i in range(v):
        d[i] = [d[i][j] if d[i][j]<INF//10 else 'INF' for j in range(v)]
        print(*d[i])

Solution (Python):
V, E = map(int, input().split())
graph = [[10**18]*V for _ in range(V)]

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

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

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

ans = True
for i in range(V):
    if graph[i][i]<0:
        ans = False
        break

if ans:
    for g in graph:
        g = [i if not i>10**17 else 'INF' for i in g]
        print(*g)
else:
    print('NEGATIVE CYCLE')

Solution (Python):






def warshall_floyd(v_num, dist_lst):

    
    negative_cycle_flag = False

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

    for v in range(v_num):
        
        
        if dist_lst[v][v] < 0:
            negative_cycle_flag = True

    if negative_cycle_flag:
        print("NEGATIVE CYCLE")
    else:
        for lst in dist_lst:
            put = ""
            for i in lst:
                if i == INF:
                    put += "INF" + " "
                else:
                    put += str(i) + " "
            print(put.rstrip())


v_num, e_num = map(int, input().split())



INF = 10 ** 20
dist_lst = [[INF] * v_num for _ in range(v_num)]

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

for v in range(v_num):
    dist_lst[v][v] = 0

warshall_floyd(v_num, dist_lst)

Solution (Python):
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,c = map(int,input().split())
    d[s][t] = 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])

for i in range(V):
    if d[i][i] != 0: 
        print('NEGATIVE CYCLE')
        exit()

for i in range(V):
    for j in range(V):
        if d[i][j] == float('inf'):
            d[i][j] = 'INF'
    print(*d[i])

Solution (Python):
N,M=map(int,input().split())
dp=[[float("inf") for _ in range(N)]for _ in range(N)]
for i in range(N):
    dp[i][i]=0
for _ in range(M):
    s,t,d=map(int,input().split())
    dp[s][t]=d

for k in range(N):
    for i in range(N):
        for j in range(N):
            dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])
flag=True
for v in range(N):
    if dp[v][v]<0:
        flag=False
        break

if flag:
    for i in range(N):
        for j in range(N):
            if dp[i][j]==float("inf"):
                dp[i][j]="INF"
    for i in range(N):
        print(*dp[i])
else:
    print("NEGATIVE CYCLE")

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


n,w = map(int,input().split()) 

d = [[float("inf") for i in range(n)] for i in range(n)] 

for i in range(w):
    x,y,z = map(int,input().split())
    d[x][y] = z 
for i in range(n):
    d[i][i] = 0 
distance=warshall_floyd(d)

for i in range(n):
    if distance[i][i]<0:
        print('NEGATIVE CYCLE')
        exit()
for i in distance:
    i=['INF' if x==float('inf') else x for x in i]
    print(*i)

Solution (Python):
from itertools import product

class FloydWarshall:
    def __init__(self, N):
        self.N = N 
        self.E = [[] for _ in range(N)]

    def add_edge(self, init, end, weight, undirected=False):
        self.E[init].append((end, weight))
        if undirected: self.E[end].append((init, weight))
    
    def distance(self):
        INF = float('inf')
        self.dist = [[INF] * self.N for _ in range(self.N)] 
        self.prev = [[-1] * self.N for _ in range(self.N)] 
        
        for v in range(self.N):
            self.dist[v][v] = 0; self.prev[v][v] = -1
            for u, c in self.E[v]: self.dist[v][u] = c; self.prev[v][u] = v
        
        for k in range(self.N):        
            for i, j in product(range(self.N), repeat=2):
                temp = self.dist[i][k] + self.dist[k][j]
                if self.dist[i][j] > temp: self.dist[i][j] = temp; self.prev[i][j] = self.prev[k][j]
        for v in range(self.N):
            if self.dist[v][v] < 0: return None 
        return self.dist
    
    def shortest_path(self, s, t):
        P = []
        prev_s = self.prev[s]
        while True:
            P.append(t)
            t = prev_s[t]
            if t == -1: break
            elif t == P[0]: P.append(t); break
        return P[::-1]

INF = float('inf')
N, M = map(int, input().split())
fw = FloydWarshall(N)
for _ in range(M):
    a, b, c = map(int, input().split())
    fw.add_edge(a, b, c)
dist = fw.distance()
if dist is None: print('NEGATIVE CYCLE')
else:
    for dst in dist: print(*[d if d != INF else 'INF' for d in dst])

Solution (Python):
v, e = map(int, input().split())

adj_mat = [[float("inf")] * v for j in range(v)]
dist = [[float("inf")] * v for j in range(v)]

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

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

for k in range(v):
    for i in range(v):
        for j in range(v):
            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 dist[i][j] == float("inf"):
            print("INF", end="")
        else:
            print("%d" % (dist[i][j]), end="")

        if j < v - 1:
            print(" ", end="")
    print()

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m = LI()
    d = [[0 if i == j else float("inf") for j in range(n)] for i in range(n)]
    for _ in range(m):
        a,b,c = LI()
        d[a][b] = c
    for k in range(n):
        for i in range(n):
            for j in range(n):
                nd = d[i][k]+d[k][j]
                if nd < d[i][j]:
                    d[i][j] = nd
    for i in range(n):
        if d[i][i] < 0:
            print("NEGATIVE CYCLE")
            return
        for j in range(n):
            if d[i][j] == float("inf"):
                d[i][j] = "INF"
    for i in d:
        print(*i,sep = " ")
    return


if __name__ == "__main__":
    solve()

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


def warshall_floid(graph: list) -> list:
    """warshall-floid法: 各頂点から各頂点への最短距離を求める
    計算量: O(V^3)
    """
    n = len(graph)
    INF = 10 ** 18
    dp = [[INF] * n for i in range(n)]
    for i in range(n):
        dp[i][i] = 0
    for i in range(n):
        for j, cost in graph[i]:
            dp[i][j] = cost

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

v, e = map(int, input().split())
info = [list(map(int, input().split())) for i in range(e)]
INF = 10 ** 18

graph = [[] for i in range(v)]
for a, b, cost in info:
    graph[a].append((b, cost))

dp = warshall_floid(graph)

is_negative = False
for i in range(v):
    if dp[i][i] < 0:
        is_negative = True

if is_negative:
    print("NEGATIVE CYCLE")
else:
    for res in dp:
        print(*[num if num < 10**12 else "INF" for num in res])

Solution (Python):
import sys


INF = sys.maxsize
V, E = map(int, input().split())

costs = [[INF] * V for _ in range(V)]

for _ in range(E):
  s, t, d = map(int, input().split())
  costs[s][t] = d
  
for i in range(V):
  costs[i][i] = 0
  
for k in range(V):
  for i in range(V):
    for j in range(V):
      if costs[i][k] == INF or costs[k][j] == INF:
        continue
      costs[i][j] = min(costs[i][j], costs[i][k] + costs[k][j])

if any(costs[i][i] < 0 for i in range(V)):
  print('NEGATIVE CYCLE')
else:
  for row in costs:
    print(' '.join('INF' if x == INF else str(x)  for x in row))

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


def check(W):
    
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if W[i][k]+W[k][j]+W[j][i]<0:
                    return False
                W[i][j] = min(W[i][j], W[i][k]+W[k][j])
    return True


if __name__ == "__main__":
    V, E = map(int, input().split())
    inf = float("inf")
    W = [[inf]*V for _ in range(V)]
    for i in range(V):
        W[i][i] = 0

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

    if check(W):
        for i in W:
            print(*(j if j!=inf else "INF" for j in i))
    else:
        print("NEGATIVE CYCLE")

Solution (Python):
import math,itertools,bisect,sys,copy,queue
sys.setrecursionlimit(10**7)
INF = 10**20

def LI(): return [int(x) for x in sys.stdin.readline().split()]

N,E = LI()
dp = [[INF for _ in range(N)] for _ in range(N)]
for i in range(N): dp[i][i] = 0
for _ in range(E):
    s,t,d = LI()
    dp[s][t] = d

for k in range(N):
    for i in range(N):
        for j in range(N):
            if dp[i][k] < INF and dp[k][j] < INF:
                dp[i][j] = min(dp[i][j],dp[i][k] + dp[k][j])

for i in range(N):
    if dp[i][i] < 0:
        print ('NEGATIVE CYCLE')
        exit(0)
for i in range(N):
    for j in range(N):
        print (dp[i][j] if dp[i][j] < INF else 'INF',end='')
        if j < N-1: print (' ',end='')
    print ('')

Solution (Python):
num_V, num_E = map(int, input().split())
INF = float('inf')
E = [[INF] * num_V for _ in range(num_V)]
for _ in range(num_E):
	ts,tt,td = map(int, input().split())
	E[ts][tt] = td
for i in range(num_V):
	E[i][i] = 0

for k in range(num_V):
	for i in range(num_V):
		for j in range(num_V):
			E[i][j] = min(E[i][j], E[i][k]+E[k][j])

cond = 0
for k in range(num_V):
	for i in range(num_V):
		for j in range(num_V):
			if E[i][j] > E[i][k]+E[k][j]:
				cond = 1
				break

if cond == 1:
	print('NEGATIVE CYCLE')
else:
	for e in E:
		print(*['INF' if e[i] == INF else e[i] for i in range(num_V)])

Solution (Python):
import sys
import math
import fractions
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = float('inf')
INF = 10 ** 18 + 7
input = lambda: sys.stdin.readline().strip()


def warshall_floyd(d):
    """
    d[i][l]がi→lへのコストを示す隣接行列
    結果としてd[i][l]はi→lへの最短コストになる。
    """
    for i in range(len(d)):
        for l in range(len(d)):
            for k in range(len(d)):
                d[l][k] = min(d[l][k], d[l][i] + d[i][k])
    return d


V, E = map(int, input().split())
std = [list(map(int, input().split())) for _ in range(E)]
d = [[INF for _ in range(V)] for _ in range(V)]
for i in range(V):
    d[i][i] = 0
for i in std:
    d[i[0]][i[1]] = i[2]

ans = warshall_floyd(d)
for i in range(V):
    if ans[i][i] < 0:
        print("NEGATIVE CYCLE")
        sys.exit()
for i in range(V):
    for l in range(V):
        if ans[i][l] > 10 ** 11:
            ans[i][l] = "INF"
        else:
            ans[i][l] = str(ans[i][l])

for i in ans:
    print(" ".join(i))

Solution (Python):
import sys

def warshall_floyd(d, n):
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    has_nagative_cycle = False
    for i in range(n):
        if d[i][i] < 0:
            has_nagative_cycle = True
            break
    for i in range(n):
        d[i][i] = 0
    return has_nagative_cycle

V, E = map(int, sys.stdin.readline().strip().split())

d = [[float("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_i = map(int, sys.stdin.readline().strip().split())
    d[s][t] = d_i

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

Solution (Python):
def warshallFloyd():
    for i in range(V):
        for j in range(V):
            if dp[j][i] == INF: continue
            for k in range(V):
                if dp[i][k] == INF: continue
                dp[j][k] = min(dp[j][k], dp[j][i] + dp[i][k])
    return
INF = 10 ** 18
V, E = map(int, input().split())
dp = [[INF for _ in range(V)] for _ in range(V)]
ansF = False
for i in range(V):
    for j in range(V):
        if i == j:
            dp[i][j] = 0


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

warshallFloyd()
for i in range(V):
    if dp[i][i] < 0:
        print('NEGATIVE CYCLE')
        exit()
        
for i in range(V):
    for j in range(V):
        if dp[i][j] == INF:
            ptmp = 'INF'
        else:
            ptmp = dp[i][j]
        if j != V - 1:
            print(ptmp, end=' ')
        else:
            print(ptmp)

Solution (Python):






from sys import stdin,setrecursionlimit










setrecursionlimit(10**6)
input=stdin.readline

def main():
    v,e=map(int,input().split())
    INF=2<<31
    d=[[INF]*v for _ in range(v)]
    for _ in range(e):
        s,t,c=map(int,input().split())
        d[s][t]=c
    r=range(v)
    for i in r:d[i][i]=0
    for i in r:
        for j in r:
            for k in r:
                if d[j][i]==INF or d[i][k]==INF:continue
                d[j][k]=min(d[j][k],d[j][i]+d[i][k])

    

    for i in r:
        if d[i][i]<0:
            print("NEGATIVE CYCLE")
            exit()

    for i in r:
        for j in r:
            
            if d[i][j]==INF: d[i][j]="INF"

    for i in d: print(*i)

if __name__=="__main__":main()

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

class Graph():
    def __init__(self,n,edge,directed=False):
        self.n = n
        self.graph = [[] for _ in range(n)]
        for e in edge:
            self.graph[e[0]].append((e[1],e[2]))
            if not directed:
                self.graph[e[1]].append((e[0],e[2]))
    def warshall_floyd(self,INF=10**18):
        dist = [[INF for j in range(self.n)] for i in range(self.n)]
        for i in range(self.n):
            dist[i][i] = 0
        for i in range(self.n):
            for j,cost in self.graph[i]:
                dist[i][j] = cost
        for k in range(self.n):
            for i in range(self.n):
                for j in range(self.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

INF = 10**18

import sys
input = sys.stdin.readline

V,E = map(int,input().split())
edge = [tuple(map(int,input().split())) for _ in range(E)]

g = Graph(V,edge,True)
D = g.warshall_floyd(INF)


for i in range(V):
    for j in range(V):
        if D[i][j] == INF: D[i][j] = 'INF'

for i in range(V):
    if D[i][i] < 0:
        print('NEGATIVE CYCLE')
        break
else:
    print('\n'.join(map(lambda d: ' '.join(map(str,d)),D)))

Solution (Python):
def floyd(dismat, v):
    for k in range(v):
        for i in range(v):
            if dismat[i][k] != float("inf"):
                for j in range(v):
                    if dismat[k][j] != float("inf"):
                        dismat[i][j] = min(dismat[i][j], dismat[i][k] + dismat[k][j])
    return dismat


def main():
    ve = input().split()
    v, e = tuple(map(int, ve))
    dismat = [[float("inf") for _ in range(v)] for _ in range(v)]
    for _ in range(e):
        std = input().split()
        s, t, d = tuple(map(int, std))
        dismat[s][t] = d
    for i in range(v):
        dismat[i][i] = 0
    dismat = floyd(dismat, v)
    for i in range(v):
        if dismat[i][i] < 0:
            print("NEGATIVE CYCLE")
            return
    for i in range(v):
        for j in range(v):
            if dismat[i][j] == float("inf"):
                dismat[i][j] = "INF"
        print(" ".join(map(str, dismat[i])))


if __name__ == "__main__":
    main()

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


INF = 2000000000


def warshallFloyd():
    global V
    for k in range(V):
        for i in range(V):
            if A[i][k] == INF:
                continue
            for j in range(V):
                if A[k][j] == INF:
                    continue
                A[i][j] = min(A[i][k] + A[k][j], A[i][j])
    


nums=list(map(int,input().split()))
V = nums[0]
E = nums[1]

A = [[INF for i in range(V)] for j in range(V)]
for i in range(V):
    A[i][i] = 0

for i in range(E):
    nums=list(map(int,input().split()))
    A[nums[0]][nums[1]] = nums[2]

warshallFloyd()

negative = False

for i in range(V):
    if A[i][i] < 0:
        negative = True

if negative:
    print("NEGATIVE CYCLE")
else:
    for i in range(V):
        for j in range(V):
            if A[i][j] == INF:
                A[i][j] = "INF"
        
    for i in range(V):
        for j in range(V-1):
            if A[i][j] == INF:
                A[i][j] = "INF"
            print(A[i][j], end = " ")
        print(A[i][V-1])

Solution (Python):
import heapq

n, m = list(map(int, input().split()))
V = [i for i in range(n)]
E = [{} for _ in range(n)]

for _ in range(m):
    ef, et, ed = list(map(int, input().split()))
    E[ef][et] = ed
    

INF = int(1e18)
pred = {i: None for i in range(n)}

d = {i: {j: INF for j in range(n)} for i in range(n)}
for u in range(n):
    d[u][u] = 0
    for v in E[u]:
        d[u][v] = E[u][v]

neg_cycle = False
for k in range(n):
    for u in range(n):
        if d[u][k] == INF:
            continue
        for v in range(n):
            if d[k][v] == INF:
                continue
            if d[u][v] > d[u][k] + d[k][v]:
                d[u][v] = d[u][k] + d[k][v]


for k in range(n):
    if d[k][k] < 0:
        print("NEGATIVE CYCLE")
        exit()

for u in range(n):
    for v in range(n):
        if d[u][v] == INF:
            print("INF", end="")
        else:
            print(d[u][v], end="")
        if v < n - 1:
            print(" ", end="")
    print()

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


class Bellmanford:
    def __init__(self, to:list, start:int, goal:int = -1):
        self.N = len(to)
        self.to = [s[:] for s in to]
        self.start = start
        self.goal = goal
        self.dist = [inf] * self.N
        self.dist[start] = 0
        self.exists_negative_cycle = False
        self.exists_negative_cycle_stog = False
        self.is_updated = [False] * self.N

    
    def update(self) -> None:
        for _ in range(self.N - 1):
            for v, s in enumerate(self.to):
                if not s: continue
                for nv, w in s:
                    if self.dist[nv] > self.dist[v] + w:
                        self.dist[nv] = self.dist[v] + w

    
    def detection(self) -> bool:
        for v, s in enumerate(self.to):
            if not s: continue
            for nv, w in s:
                if self.dist[nv] > self.dist[v] + w:
                    self.dist[nv] = self.dist[v] + w
                    self.exists_negative_cycle = True
        return self.exists_negative_cycle

    
    def detection_stog(self) -> bool:
        for _ in range(self.N):
            for v, s in enumerate(self.to):
                if not s: continue
                for nv, w in s:
                    if self.dist[nv] > self.dist[v] + w:
                        self.dist[nv] = self.dist[v] + w
                        self.is_updated[nv] = True
                    if self.is_updated[v] is True:
                        self.is_updated[nv] = True
        self.exists_negative_cycle_stog = self.is_updated[self.goal]
        return self.exists_negative_cycle_stog

inf = float('inf')


class Warshallfloyd:
    def __init__(self, admat:list):
        self.N = len(admat)
        self.dist = [c[:] for c in admat]

    def update(self) -> None:
        for k in range(self.N):
            for i in range(self.N):
                for j in range(self.N):
                    if i == j:
                        self.dist[i][j] = 0
                    elif self.dist[i][j] > self.dist[i][k] + self.dist[k][j]:
                        self.dist[i][j] = self.dist[i][k] + self.dist[k][j]

N, M = map(int,input().split())
to = [[] for _ in range(N)]
admat = [[inf] * N for _ in range(N)]
for _ in range(M):
    s, t, d = map(int,input().split())
    to[s].append((t, d))
    admat[s][t] = d

BF = Bellmanford(to, 0)
BF.update()
if BF.detection():
    print("NEGATIVE CYCLE")
    exit()
WF = Warshallfloyd(admat)
WF.update()
ans_list = [[-1] * N for _ in range(N)]
for i in range(N):
    for j in range(N):
        ans_list[i][j] = WF.dist[i][j] if WF.dist[i][j] != inf else "INF"

for ans in ans_list:
    print(*ans)

Solution (Python):
v,e = map(int,input().split())
cost = []
for i in range(v):
    T = [float('inf')]*v
    T[i] = 0
    cost.append(T)
for i in range(e):
    a,b,c = map(int,input().split())
    cost[a][b] = c
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])
flag = True
for i in range(v):
    for j in range(v):
        if cost[i][j] == float('inf'):
            cost[i][j] = 'INF'
        elif i == j and cost[i][j] < 0:
            flag = False
            break
if flag:
    for i in range(v):
        print(' '.join(map(str,cost[i])))
else:
    print('NEGATIVE CYCLE')

Solution (Python):








from copy import deepcopy

INF = 2**36 - 1


def warchall_floyed(adj_mat: list):
    '''
    隣接行列を受け取る(隣接していないノード間のコストはINFを前提)
    全点間の最短距離を示す行列を返す。
    '''
    n = len(adj_mat)
    ret = deepcopy(adj_mat)
    for k in range(n):  
        for i in range(n):  
            if ret[i][k] == INF:
                
                continue
            for j in range(n):  
                if ret[k][j] == INF:
                    continue
                ret[i][j] = min(ret[i][j], ret[i][k] + ret[k][j])
                
    return ret  


n_V, n_E = list(map(int, input().split()))
adj_mat = [[INF] * n_V for _ in range(n_V)]  

for ij in range(n_V):
    adj_mat[ij][ij] = 0
for _ in range(n_E):
    s, t, d = list(map(int, input().split()))
    adj_mat[s][t] = d

ans = warchall_floyed(adj_mat)


for ij in range(n_V):
    if ans[ij][ij] < 0:
        print('NEGATIVE CYCLE')
        exit()

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

Solution (Python):
V,E = map(int,input().split())
INF = 10**20
D = [[INF]*V for _ in range(V)]

for i in range(V):
    D[i][i] = 0
for _ 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][k] != INF and D[k][j] != INF:
                D[i][j] = min(D[i][j],D[i][k]+D[k][j])

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

if negativecycle:
    print('NEGATIVE CYCLE')
else:
    for i in range(V):
        for  j in range(V):
            if j != 0:
                print(' ',end='')
            if D[i][j] == INF:
                print('INF',end='')
            else:
                print(D[i][j],end='')
        print('')

Solution (Python):


import os
import sys


INF = 2 * 10 ** 9 + 1


def main():
    V, E = read_ints()
    G = [[INF] * V for _ in range(V)]
    for _ in range(E):
        s, t, d = read_ints()
        G[s][t] = d
    ans = solve(V, E, G)
    if not ans:
        print('NEGATIVE CYCLE')
    else:
        for a in ans:
            print(*a)


def solve(V, E, G):
    dists = [[INF] * V for _ in range(V)]
    for i in range(V):
        for j in range(V):
            if i == j:
                dists[i][j] = 0
            elif G[i][j] != INF:
                dists[i][j] = G[i][j]

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

    for i in range(V):
        if dists[i][i] < 0:
            return None

    for i in range(V):
        for j in range(V):
            if dists[i][j] == INF:
                dists[i][j] = 'INF'
    return dists





DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def read_int():
    return int(inp())


def read_ints():
    return [int(e) for e in inp().split()]


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


if __name__ == '__main__':
    main()

Solution (Python):
import sys

readline = sys.stdin.buffer.readline


def main():
	v, e = map(int, readline().split())
	g = [[1 << 60] * v for _ in range(v)]
	for i in range(v):
		g[i][i] = 0
	for _ in range(e):
		s, t, c = map(int, readline().split())
		g[s][t] = c
	for k in range(v):
		for i in range(v):
			for j in range(v):
				if g[i][j] > g[i][k] + g[k][j]:
					g[i][j] = g[i][k] + g[k][j]
	for i in range(v):
		if g[i][i] < 0:
			print("NEGATIVE CYCLE")
			exit()
	for l in g:
		print(" ".join(["INF" if x > 1 << 40 else str(x) for x in l]))


if __name__ == "__main__":
	main()

Solution (Python):
import argparse
import sys
inf = float('inf')
from itertools import product


def washall_floyd(d):
    for k, i, j in product(range(n_node), repeat=3):
        d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d


def have_negative_loop(dist_mat):
    for i in range(n_node):
        if dist_mat[i][i] < 0:
            return True

    return False


if __name__ == "__main__":
    parser = argparse.ArgumentParser()
    parser.add_argument('--input', type=str)
    args = parser.parse_args()
    edge_input = []
    if args.input:
        f = open(args.input, 'r')
        n_node, n_edge = tuple(map(int, f.readline().split()))
        
        if n_node > 0:
            dist_mat = [[inf for _ in range(n_node)] for _ in range(n_node)]
            for _ in range(n_edge):
                from_node, to_node, cost = tuple(map(int, f.readline().split()))
                dist_mat[from_node][to_node] = cost
        f.close()
            
    else:
        n_node, n_edge = tuple(map(int, input().split()))
        dist_mat = \
            [[0 if i==j else inf for i in range(n_node)] for j in range(n_node)]
        if n_edge > 0:            
            for _ in range(n_edge):
                from_node, to_node, cost = tuple(map(int, input().split()))
                dist_mat[from_node][to_node] = cost

    dist_mat = washall_floyd(dist_mat)
    if have_negative_loop(dist_mat):
        print('NEGATIVE CYCLE')
    else:
        for i in range(n_node):
            dist = ' '.join(['INF' if j==inf else str(j) for j in dist_mat[i]])
            print(dist)

Solution (Python):
def warshallFloyd():
	for k in range(n):
		for i in range(n):
			if A[i][k] == INF:
				continue
			for j in range(n):
				if A[k][j] == INF:
					continue
				A[i][j] = min(A[i][j], A[i][k] + A[k][j])

INF = 2 * 10**9 + 89

if __name__ == "__main__":
	n, m = map(int, input().split())
	A = [[INF for _ in range(n)] for _ in range(n)]
	for i in range(n):
		A[i][i] = 0
	
	for _ in range(m):
		s, t, d = map(int, input().split())
		A[s][t] = d

	warshallFloyd()

	negative = False
	for i in range(n):
		if A[i][i] < 0:
			negative = True

	if negative:
		print("NEGATIVE CYCLE")
	else:
		for i in range(n):
			for j in range(n):
				if A[i][j] == INF:
					A[i][j] = "INF"
		for i in range(n):
			print(*A[i])

Solution (Python):

import sys

debug = False
v, e = map(int, sys.stdin.readline().strip().split())

g = [[float('inf')] * v for _ in range(v)]
for _ in range(e):
    s, t, d = map(int, sys.stdin.readline().strip().split())
    if debug: print('s : {}  t : {}'.format(s, t))
    g[s][t] = d

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

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

negative = False
for i in range(v):
    if g[i][i] < 0:
        negative = True
        break

if not negative:
    for i in range(v):
        ans = ' '.join(list(map(str, g[i])))
        ans = ans.replace('inf', 'INF')
        print(ans)
else:
    print('NEGATIVE CYCLE')