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):
from itertools import product

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

INF = 10 ** 10


def _str(n):
    if n == INF:
        return 'INF'
    else:
        return str(n)


def _add(a, b):
    if INF in (a, b):
        return INF
    return a + b


dp = []
for _ in range(V):
    dp.append([INF] * V)

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

for _ in range(E):
    a, b, d = map(int, input().split(' '))
    dp[a][b] = d

for k, i, j in product(range(V), repeat=3):
    dp[i][j] = min(dp[i][j], _add(dp[i][k], dp[k][j]))

results = []
for v in range(V):
    if dp[v][v] < 0:
        print('NEGATIVE CYCLE')
        break
    results.append(' '.join(map(_str, dp[v])))
else:
    print('\n'.join(results))

Solution (Python):



import sys
v, e = map(int, input().split())

dist = [[float('inf')] * v for _ in range(v)]

for _ in range(e):
    f, t, d = map(int, input().split())
    dist[f][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):
            
            
            if dist[i][k] != float('inf') and dist[k][j] != float('inf'):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

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

if negative:
    print('NEGATIVE CYCLE')
    sys.exit()

for i in dist:
    print(' '.join(map(lambda x: 'INF' if x == float('inf') else str(x), i)))

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq

INF = float("inf")











V,E = map(int,input().split())
INF = float("inf")
cost = [[INF]*V for _ in range(V)]
for i in range(V):
    cost[i][i] = 0
for _ in range(E):
    s,t,dd = map(int,input().split())
    cost[s][t] = dd

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])
judge = 0
for i in range(V):
    if judge == 1:
        break
    for j in range(i+1,V):
        
        if cost[i][j] + cost[j][i] < 0:
            judge = 1
            break
for i in range(V):
    for j in range(V):
        if cost[i][j] == INF:
            cost[i][j] = "INF"
        else:
            cost[i][j] = str(cost[i][j])
if judge == 1:
    print("NEGATIVE CYCLE")
else:
    for i in range(V):
        print(*cost[i])

Solution (Python):


import re
import math
from collections import defaultdict
from collections import deque
import collections
from fractions import Fraction
from queue import PriorityQueue
import itertools
from copy import deepcopy
import random
import time
import os
import sys
import datetime
from functools import lru_cache
from functools import reduce
readline=sys.stdin.readline
sys.setrecursionlimit(2000000)
alphabet="abcdefghijklmnopqrstuvwxyz"
mod=int(10**9+7)
inf=int(10**19)
class Edge():
    def __init__(self,x,y,cost=1):
        self.x=x
        self.y=y
        self.cost=cost
def yn(b):
    if b:print("yes")
    else:print("no")
def Yn(b):
    if b:print("Yes")
    else:print("No")
def YN(b):
    if b:print("YES")
    else:print("NO")
class unionfind():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(n)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):
            self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def ispow(a,b):
    now=b
    while now<a:
        now*=b
    return now==a
def getbin(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def getfacs(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod_>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def nextcomb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:return num
def getprimes(n,type="int"):
    if n==0:
        if type=="int":return []
        else:return [False]
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    if(type=="bool"):return A
    B=[]
    for a in range(n+1):
        if(A[a]):B.append(a)
    return B
def isprime(num):
    if(num<=1):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def ifelse(bbool,ret1,ret2):
    if bbool:return ret1
    else:return  ret2
def join(A,c=" "):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s
def factorize(n,type_="dict"):
    b = 2
    list_ = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            list_.append(b)
        b+=1
    if n > 1:list_.append(n)
    if type_=="dict":
        dic={}
        for a in list_:
            if a in dic:
                dic[a]+=1
            else:
                dic[a]=1
        return dic
    elif type_=="list":
        return list_
    else:
        return None
def pm(x):
    return x//abs(x)
def inputintlist(): 
    return list(map(int,input().split()))
def istanchouzouka(A):
    f=True
    prev=min(A)-1
    for a in A:
        if prev>=a:
            f=False
        prev=a
    return f
def istanchouhigensyou(A):
    f=True
    prev=min(A)-1
    for a in A:
        if prev>a:
            f=False
        prev=a
    return f
def getallsum(A):
    s=sum(A)
    dp=defaultdict(int)
    dp[0]=1
    for a in range(0,len(A)):
        for b in range(s,-1,-1):
            if b-A[a]>=0:
                dp[b]+=dp[b-A[a]]
    return dp
def lcm(a,b):
    return a*b//math.gcd(a,b)
    G=[[] for a in range(n)]
    for edge in edges:
        x=edge[0]
        y=edge[1]
        G[x].append(y)
        if mukou:G[y].append(x)
    return G
def yuukoutomukou(edges):
    ret=deepcopy(edges)
    for edge in edges:
        if not edge.x==edge.y:
            ret.append(Edge(edge.y,edge.x,edge.cost))
    return ret
def dijkstra(edges,V,start):
    mincost=[inf]*V
    G=[[] for a in range(V)]
    for edge in edges:
        G[edge.x].append([edge.cost,edge.y])
    Q=PriorityQueue()
    Q.put([0,start])
    while not Q.empty():
        nowcost,nowx=Q.get()
        if mincost[nowx]==inf:
            mincost[nowx]=nowcost
            for cost,y in G[nowx]:
                newcost=nowcost+cost
                Q.put([newcost,y])
    return mincost
def warshallfloyd(edges,V):
    mincost=[[inf for b in range(V)] for a in range(V)]
    for a in range(V):mincost[a][a]=0
    for edge in edges:
        mincost[edge.x][edge.y]=min(mincost[edge.x][edge.y],edge.cost)
    for k in range(V):
        for s in range(V):
            for t in range(V):
                if mincost[s][k]==inf or mincost[k][t]==inf:continue
                mincost[s][t]=min(mincost[s][t],mincost[s][k]+mincost[k][t])
                
                if s==t and mincost[s][t]<0:
                    return "negative cycle"
    return mincost

V,E=inputintlist()
edges=[]
for a in range(E):
    e=Edge(*inputintlist())
    edges.append(e)

mincost=warshallfloyd(edges,V)

if mincost=="negative cycle":
    print(mincost.upper())
else:
    for a in range(V):
        for b in range(V):
            if mincost[a][b]==inf:mincost[a][b]="INF"
    for a in range(V):
        print(join(mincost[a]))

Solution (Python):
V, E = map(int, input().split())
INF = 10**12
dp = [[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):
      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(V):
  if dp[i][i] < 0:
    print('NEGATIVE CYCLE')
    exit()
        
for i in range(V):
  print(*['INF' if d == INF else d for d in dp[i]])

Solution (Python):
v, e = map(int, input().split())
g = [[] for _ in range(v)]
dp = [[float("inf")] * v for _ in range(v)]
for i in range(v):
    dp[i][i] = 0
for i 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])
            if i == j and dp[i][j] < 0:
                print("NEGATIVE CYCLE")
                exit()

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

Solution (Python):
def warshall_floyd(d):
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
              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


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

d = [[float("INF")] * 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 

D = warshall_floyd(d)
for i in range(n):
  if D[i][i] < 0:
    print("NEGATIVE CYCLE")
    
    quit()
    
for i in range(n):
  for j in range(n):
    if D[i][j] == float("inf"):
      if j == n - 1:
        D[i][j] = print("INF")
      else:
        D[i][j] = print("INF", end = " ")
    else:
      if j == n - 1:
        print(D[i][j])
      else:
        print(D[i][j], end = " ")

Solution (Python):
V,E = map(int,input().split())
INF = 2*10**10
C = [[INF]*V for _ in range(V)]
for i in range(E):
    tmp = list(map(int,input().split()))
    C[tmp[0]][tmp[1]] = tmp[2]

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

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

negative_cycle_f = False
for i in range(V):
    if C[i][i] < 0:
        negative_cycle_f = True

if negative_cycle_f:
    print("NEGATIVE CYCLE")
else:
    for i in range(V):
        for j in range(V):
            if C[i][j] == INF:
                print("INF",end="")
            else:
                print("{}".format(C[i][j]),end="")
            if j != V-1:
                print(" ",end="")
        print("")

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])
            if i == j and dp[i][i] < 0:
                print("NEGATIVE CYCLE")
                exit()

for i in range(V):
    ans = []
    for j in range(V):
        if dp[i][j] == float("inf"):
            ans.append("INF")
        else:
            ans.append(dp[i][j])
    print(*ans)

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

INF=float('inf')
D=[[INF]*v for index2 in range(v)]
for index3 in range(v):
    D[index3][index3]=0
for index1 in range(e):
    s,t,d=map(int,input().split())
    D[s][t]=d
    


def warshall_floyd():
    global 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])
    
    return D

ans=warshall_floyd()
for index4 in range(v):
    if ans[index4][index4]<0:
        print('NEGATIVE CYCLE')
        break
else:
    for index5 in range(v):
        List=[]
        for index6 in range(v):
            if ans[index5][index6]==INF:
                List.append('INF')
            else:
                List.append(ans[index5][index6])
        print(*List)

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

V, E = map(int, input().split())
A = [[INF] * V for _ in range(V)]

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

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

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][j], A[i][k] + A[k][j])

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):
        ans_row = []
        for j in range(V):
            if A[i][j] == INF:
                ans_row.append('INF')
            else:
                ans_row.append(A[i][j])
        print(*ans_row)

Solution (Python):
import sys, heapq
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
MOD = 1000000007
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def warshall_floyd(d):
    V = len(d)
    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])
    return d

def resolve():
    V, E = LI()
    con = [[INF]*V for _ in range(V)]
    for _ in range(E):
        s, t, d = LI()
        con[s][t] = d

    ans = warshall_floyd(con)

    has_ns = [ans[i][i]<0 for i in range(V)].count(True)>0
    if has_ns:
        print('NEGATIVE CYCLE')
    else:
        for i in ans:
            print(' '.join([str(j) if j<INF else 'INF' for j in i]))

if __name__ == '__main__':
    resolve()

Solution (Python):
import sys
input = sys.stdin.readline
INF = float('inf')


def main():
    V, E = map(int, input().split())
    dist = [[0 if i == j else INF for j in range(V)] for i 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):
                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 j in range(V):
            if dist[i][j] == INF:
                dist[i][j] = 'INF'
    for l in dist:
        print(*l)


if __name__ == '__main__':
    main()

Solution (Python):







import sys,collections
N,E = tuple(map(int,sys.stdin.readline().split())) 

INF = float("inf")
ALL = set(range(N))

distances = [[INF]*N for _ in range(N)]
for i in range(N):
  distances[i][i] = 0

for i in range(E):
  s,d,w = (map(int,sys.stdin.readline().rstrip().split()))
  distances[s][d] = w


def warshallFloyd():
  for k in range(N):
    for i in range(N):
      for j in range(N):
        distances[i][j] = min(distances[i][j], distances[i][k] + distances[k][j])

warshallFloyd()

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

for i in range(N):
  s = []
  for j in range(N):
    if distances[i][j] == INF:
      s.append("INF")
    else:
      s.append(str(distances[i][j]))
  print(" ".join(s))

Solution (Python):
V,E = map(int,input().split())
dlist = [[0]*V for _ in range(V)]
dp = [[10**11]*V for _ in range(V)]




for _ in range(E):
  el = list(map(int,input().split()))
  dlist[el[0]][el[1]] = el[2]
  dp[el[0]][el[1]] = el[2]

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")
    exit()
      
for i in range(V):
  for j in range(V):
    if dp[i][j] >= 10**10:
      dp[i][j] = "INF"
      
for i in range(V):
  print(*dp[i])

Solution (Python):
"""
ワーシャルフロイド法:O(n^3)
n:頂点数
"""
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


inf = float('inf')
n, w = [int(x) for x in input().split()] 
d = [[inf]*n for _ in range(n)]
for i in range(n):
    d[i][i] = 0
for _ in range(w):
    x, y, z = [int(x) for x in input().split()] 
    d[x][y] = z
    
d = warshall_floyd(d)
for i in range(n):
    if d[i][i] < 0:
        print("NEGATIVE CYCLE")
        exit()
for i in d:
    print(" ".join([str(x) for x in i]).replace("inf", "INF"))

Solution (Python):

Vn, En = map(int, input().split())



INF = float("inf")

E = [[INF]*Vn for _ in range(Vn)]
for _ in range(En):
    s, t, c = map(int, input().split())
    E[s][t] = c

for i in range(Vn):
    E[i][i] = 0

for k in range(Vn):
    for i in range(Vn):
        for j in range(Vn):
            E[i][j] = min(E[i][j], E[i][k]+E[k][j])
f = False
for i in range(Vn):
    if E[i][i] < 0:
        f = True
        break
    
if f:
    print("NEGATIVE CYCLE")
else:
    for i in range(Vn):
        for j in range(Vn):
            if E[i][j] == INF:
                E[i][j] = "INF"
        print(" ".join(map(str,E[i])))

Solution (Python):
v, e = map(int, input().split())
G = [[float('inf') for _ in range(v)] for i in range(v)]
for i in range(v):
    G[i][i] = 0

dist = [[float('inf') for i in range(v)] for j in range(v)]
for _ 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]) 
            if i == j and dist[i][j] < 0:
                print('NEGATIVE CYCLE')
                exit()
ans = [["INF"]*v for _ in range(v)]
for i in range(v):
    for j in range(v):
        if dist[i][j] != float('inf'):
            ans[i][j] = dist[i][j]
for i in range(v):
    print(*ans[i])

Solution (Python):

N, M = map(int, input().split())
d = [[float('inf')]*N for _ in range(N)]
for i in range(M): 
    a,b,t = map(int, input().split())
    d[a][b] = t

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

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])
            if i==j and d[i][i]<0:
                print('NEGATIVE CYCLE')
                exit()

for i in range(N):
    ans = []
    for j in range(N):
        if d[i][j]==float('inf'):
            ans.append('INF')
        else:
            ans.append(str(d[i][j]))
    print(' '.join(ans))

Solution (Python):


from pprint import pprint
from collections import deque, defaultdict
import itertools
import math
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.buffer.readline
INF = float("inf")

n_nodes, m_edges = map(int, input().split())

edges = [[] for _ in range(n_nodes)]
for _ in range(m_edges):
    s, t, d = map(int, input().split())
    edges[s].append([t, d])



def floyd_warshall(n_nodes, edges):
    dist = [[INF for u in range(n_nodes)] for v in range(n_nodes)]
    for u, e in enumerate(edges):
        for v, cost in e:
            dist[u][v] = cost
    for v in range(n_nodes):
        dist[v][v] = 0
    for k in range(n_nodes):
        for s in range(n_nodes):
            for t in range(n_nodes):
                dist[s][t] = min(dist[s][t], dist[s][k] + dist[k][t])
    return dist


dist = floyd_warshall(n_nodes, edges)


has_negative_cycle = False
for v in range(n_nodes):
    if dist[v][v] < 0:
        has_negative_cycle = True
        break

for u in range(n_nodes):
    for v in range(n_nodes):
        if dist[u][v] == INF:
            dist[u][v] = 'INF'


if has_negative_cycle:
    print('NEGATIVE CYCLE')
else:
    for d in dist:
        print(*d)

Solution (Python):




from heapq import heappop, heappush
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines


class BellmanFord:
    """
    shortest_distance(): startノードから各ノードまでの最短距離
    include_negative_cycle(): 負閉路の存在確認
    """
    def __init__(self, V, edges, start):
        """
        V : 頂点数
        edges: (辺の始点,辺の終点,辺のコスト)を要素とする辺のリスト
        start: 始点のノード番号
        """
        self.V = V
        self.edges = edges
        self.start = start

    def include_negative_cycle(self):
        """
        負閉路の存在確認
        Returns: True or False
        """
        d = [0] * self.V
        for i in range(self.V):
            
            for s, e, c in self.edges:
                if d[e] > d[s] + c:
                    d[e] = d[s] + c
                    
                    if i == self.V-1:
                        return True
        return False
                    
    def shortest_distance(self):
        """ 
        始点から各頂点までの最短距離をを返す
        負閉路に到達可能ならば d[start] = INF
        """
        d = [float('inf')] * self.V
        d[self.start] = 0

        loop_counter = 0
        while True:
            update = False
            
            for s, e, c  in self.edges:
                if d[s] != float('inf') and d[e] > d[s] + c:
                    d[e] = d[s] + c
                    update = True
            
            
            
            loop_counter += 1
            if loop_counter == self.V and update:
                d[self.start] = float('inf')
                break

            if not update:
                break
        
        return d


class Dijkstra:
    """
    shortest_distance(): startノードから各ノードまでの最短距離
    """
    def __init__(self, graph, start):
        """
        graph: 隣接リストによるグラフ
        start: 始点のノード番号
        """
        self.g = graph
        self.V = len(graph)

        
        
        self.dist = [float('inf')] * self.V
        self.dist[start] = 0

        
        self.Q = []
        heappush(self.Q, (0, start))

        while self.Q:
            
            dist_u, u = heappop(self.Q)
            if dist_u > self.dist[u]:
                continue
            for v, weight in self.g[u]:
                alt = self.dist[u] + weight
                if alt < self.dist[v] :
                    self.dist[v] = alt
                    heappush(self.Q, (alt, v))

    def shortest_distance(self):
        return self.dist


def main():
    V,E,*std = map(int, read().split())

    Edges = []
    for i in range(V):
        Edges.append((V, i, 0))

    for s,t,d in zip(*[iter(std)]*3):
        Edges.append((s, t, d))
    
    
    bf = BellmanFord(V+1, Edges, V)
    h = bf.shortest_distance()
    
    if float('inf') in h:
        print("NEGATIVE CYCLE")
    else:
        Graph = [[] * V for _ in range(V)]
        for s, t, d in Edges:
            if s == V:
                continue
            else:
                Graph[s].append((t, d + h[s] - h[t]))
        
        ans = []
        
        for i in range(V):
            d = Dijkstra(Graph, i)
            ans.append(d.shortest_distance())
    
        
        for i, line in enumerate(ans):
            h_i = h[i]
            for j, n in enumerate(line):
                if n == float('inf'):
                    line[j] = "INF"
                else:
                    line[j] -= h_i - h[j]
            tmp = " ".join(map(str, line))
            print(tmp)


if __name__ == "__main__":
    main()

Solution (Python):
INF = float('inf')
V, E = map(int, input().split())
dist = [[INF] * V for _ in range(V)] 
for i in range(E):
  s, t, d = map(int, input().split())
  dist[s][t] = d
for j in range(V):
  dist[j][j] = 0
for k in range(V):
  for l in range(V):
    for m in range(V):
      dist[l][m] = min(dist[l][m], dist[l][k]+dist[k][m])
flag = 0
for i in range(V):
  if(dist[i][i] < 0):
    flag = 1
    print('NEGATIVE CYCLE')
    break
if(flag == 0):
  for i in range(V):
    for j in range(V):
      if(dist[i][j] == INF):
        dist[i][j] = 'INF'
    print(*dist[i])

Solution (Python):
def warshalFloyd(v,e):
    inf=float("inf")
    G=[[inf if i!=j else 0 for i in range(v)] for j in range(v)]

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

    return G


v,e=map(int,input().split())
Graph=warshalFloyd(v,e)

for i in range(v):
    if Graph[i][i]<0:
        print("NEGATIVE CYCLE");exit()

for i in range(v):
    Graph[i]=list(map(str,Graph[i]))
    for j in range(v):
        if Graph[i][j]=="inf":
            Graph[i][j]="INF"

for i in range(v):
    print(*Graph[i])

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


INF = sys.maxsize



def main():
    v, e = map(int, input().split())
    dist_mat = [[INF if i != j else 0 for i in range(v)] for j in range(v)]

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

    negative = False
    for k in range(v):
        for i in range(v):
            for j in range(v):
                dist_mat[i][j] = min(dist_mat[i][j],
                                     dist_mat[i][k] + dist_mat[k][j] if dist_mat[i][k] < INF and dist_mat[k][
                                         j] < INF else INF)
                if i == j and dist_mat[i][j]<0:
                    negative = True
                    print("NEGATIVE CYCLE")
                    exit(0)

    for d in dist_mat:
        for i in range(v):
            if d[i] == INF:
                d[i] = "INF"
        print(*d, sep=" ")


if __name__ == '__main__':
    main()

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

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

n,e=map(int,input().split())
l=[[INFTY for i in range(n)] for i in range(n)]
for i in range(n):
    l[i][i]=0

for i in range(e):
    a,b,c=map(int,input().split())
    l[a][b]=c

distance=warshallFloyd(l,n)

negative=False

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

if negative:
    print("NEGATIVE CYCLE")
else:
    for i in range(n):
        for j in range(n):
            if j:
                print(" ",end='')
            if l[i][j]==INFTY:
                print("INF",end='')
            else:
                print(l[i][j],end='')
        print()

Solution (Python):
v,e = map(int,input().split())
INF = float("INF")
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):
        if D[i][k] == INF: continue 
        for j in range(v):
            if D[k][j] == INF: continue
            D[i][j] = min(D[i][j],D[i][k]+D[k][j])

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

if neg:
    print("NEGATIVE CYCLE")
else:
    for i in range(v):
            print(" ".join(map(lambda x:"INF" if x == INF else str(x),D[i])))

Solution (Python):
V, E = map(int, input().split())
cost = [[float('inf') for _ in range(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])

ans = [[] for _ in range(V)]




ok = True
for i in range(V):
    if cost[i][i] != 0:
        ok = False
if ok:
    for i in range(V):
        for j in range(V):
            if cost[i][j] != float('inf'):
                ans[i].append(cost[i][j])
            else:
                ans[i].append('INF')
    for i in range(V):
        print(*ans[i])
else:
    print('NEGATIVE CYCLE')

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

INF = float('inf')
    
def warshall_floyd(V, dist):
    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])
    return dist

def check_negative_cycle(V, dist):
    dist = warshall_floyd(V, dist)
    
    for i in range(V):
        if dist[i][i] != 0: return dist, True
        
    return dist, False

def main():
    V, E = list(map(int, input().split()))
    
    dist = [[INF for i in range(V)] for j in range(V)]
    
    for i in range(V): dist[i][i] = 0
    
    for i in range(E):
        s, t, d = list(map(int, input().split()))
        dist[s][t] = min(dist[s][t], d)
    
    dist, negative_cycle = check_negative_cycle(V, dist)
    
    if negative_cycle: print('NEGATIVE CYCLE')
    else: 
        for i in range(V):
            for j in range(V):
                if dist[i][j] == INF: dist[i][j] = 'INF'
            print(' '.join(map(str, dist[i])))

if __name__ == '__main__':
    main()

Solution (Python):
V, E = map(int, input().split())
G = [[] for _ in range(V)]
for _ in range(E):
    s, t, d = map(int, input().split())
    G[s].append((t, d))

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

for i in range(V):
    dp[i][i] = 0
    for j, d in G[i]:
        dp[i][j] = 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])


if all([dp[i][i] == 0 for i in range(V)]):
    for l in dp:
        print(*[d if d != float('inf') else 'INF' for d in l])
else:
    print('NEGATIVE CYCLE')