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
import os
import pprint

"""???????????£????????????????????¨??????"""

MAX = 100
d = [[None for i in range(MAX)] for j in range(MAX)]

for i in range(MAX):
    for j in range(MAX):
        if i == j:
            d[i][j] = 0
        else:
            d[i][j] = float('inf')





V, E = list(map(int, input().split()))
for i in range(E):
    start, end, weight = list(map(int, input().split()))
    d[start][end] = weight


for k in range(V):
    for i in range(V):
        for j in range(V):
            if d[i][k] == float('inf'):
                continue
            elif d[k][j] == float('inf'):
                continue
            else:
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])


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

if negative:
    print('NEGATIVE CYCLE')
else:
    for i in range(V):
        for j in range(V):

            if d[i][j] == float('inf'):
                print("INF", end="")
            else:
                print(d[i][j], end='')
            if j != V - 1:
                print(' ', end='')
            else:
                print('')

Solution (Python):
import sys
from operator import itemgetter

inf = 1<<60

def solve():
    N, M = map(int, sys.stdin.readline().split())

    cost = [[inf]*N for i in range(N)]
    for u in range(N):
        cost[u][u] = 0

    for i in range(M):
        si, ti, di = map(int, sys.stdin.readline().split())
        cost[si][ti] = di

    res = WarshallFloyd(N, cost)

    if res is None:
        print('NEGATIVE CYCLE')
    else:
        for i in range(N):
            print(*[res[i][j] if res[i][j] < inf else 'INF' for j in range(N)])


def WarshallFloyd(N, cost):
    dist = [[inf]*N for i in range(N)]

    for i in range(N):
        for j in range(N):
            dist[i][j] = cost[i][j]

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

    if any(dist[i][i] < 0 for i in range(N)):
        return None
    else:
        return dist

if __name__ == '__main__':
    solve()

Solution (Python):
import sys

inf = float('inf')

def solve():
    N, M = map(int, sys.stdin.readline().split())

    cost = [[inf]*N for i in range(N)]
    for u in range(N):
        cost[u][u] = 0

    for i in range(M):
        si, ti, di = map(int, sys.stdin.readline().split())
        cost[si][ti] = di

    res = WarshallFloyd(N, cost)

    if res is None:
        print('NEGATIVE CYCLE')
    else:
        for i in range(N):
            print(*[res[i][j] if res[i][j] < inf else 'INF' for j in range(N)])


def WarshallFloyd(N, cost):
    dist = [[inf]*N for i in range(N)]

    for i in range(N):
        for j in range(N):
            dist[i][j] = cost[i][j]

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

    if any(dist[i][i] < 0 for i in range(N)):
        return None
    else:
        return dist

if __name__ == '__main__':
    solve()

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

d = [[0 if i == j else inf for i in range(V)] for j in range(V)]

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

def wf():
    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])
wf()

flag = True
for i in range(V):
    if d[i][i] < 0:
        flag = False
        break
if flag:
    for i in range(V):
        print(" ".join("INF" if j == inf else str(j) for j in d[i]))
else: print("NEGATIVE CYCLE")

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

V, E = map(int, readline().split())
inf = 10**10
vertices = [[inf if i!=j else 0 for j in range(V)] for i in range(V)]

for _ in [None]*E:
    s, t, d = map(int, readline().split())
    vertices[s][t] = d

for k in range(V):
    for i in range(V):
        for j in range(V):
            c1, c2, c3 = vertices[i][j], vertices[i][k], vertices[k][j]
            if c2 != inf and c3 != inf:  
                vertices[i][j] = c1 if c1 < c2+c3 else c2+c3

ans = []
for i, a in enumerate(vertices):
    if a[i] < 0:
        print("NEGATIVE CYCLE")
        break
    ans.append(" ".join([str(n) if n != inf else "INF" for n in a]))
else:
    print("\n".join(ans))

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

V, E = map(int, readline().split())
inf = float("inf")
vertices = [[inf if i!=j else 0 for j in range(V)] for i in range(V)]

for _ in [None]*E:
    s, t, d = map(int, readline().split())
    vertices[s][t] = d

for k in range(V):
    for i in range(V):
        for j in range(V):
            c1, c2, c3 = vertices[i][j], vertices[i][k], vertices[k][j]
            vertices[i][j] = c1 if c1 < c2+c3 else c2+c3

ans = []
for i, a in enumerate(vertices):
    if a[i] < 0:
        print("NEGATIVE CYCLE")
        break
    ans.append(" ".join([str(n) if n != inf else "INF" for n in a]))
else:
    print("\n".join(ans))

Solution (Python):
def main():
    nvertices, nedges = map(int, input().split())
    INF = float('inf')
    D1 = [[INF for i in range(nvertices)] for i in range(nvertices)]
    for i in range(nedges):
        s, t, d = map(int, input().split())
        D1[s][t] = d

    for i in range(nvertices):
        D1[i][i] = 0

    for k in range(nvertices):
        D2 = [[INF for i in range(nvertices)] for i in range(nvertices)]
        for i in range(nvertices):
            for j in range(nvertices):
                D2[i][j] = min(D1[i][j], D1[i][k] + D1[k][j])
        D1 = D2

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

    for lst in D1:
        print(" ".join(map(lambda e: str(e) if e < INF else "INF", lst)))


main()

Solution (Python):
from sys import stdin
MAX = 100
INF = 1<<32
n, e = map(int, stdin.readline().split())
d = [[INF] * n for _ in range(n)]
for i in range(n):
    d[i][i] = 0
for i in range(e):
    u, v, c = map(int, stdin.readline().split())
    d[u][v] = c
def floyd():
    for k in range(n):
        for i in range(n):
            if d[i][k] == INF: continue
            for j in range(n):
                if d[k][j] == INF: continue
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
floyd()
for i in range(n):
    if d[i][i] < 0:
        print("NEGATIVE CYCLE")
        exit(0)
for i in range(n):
    for j in range(n):
        if d[i][j] == INF: print("INF", end="")
        else: print(d[i][j], end="")
        if j + 1 != n:
            print(" ", end="")
    print()

Solution (Python):
from sys import stdin
from math import isinf
n, e = map(int, stdin.readline().split())
d = [[float('inf')] * n for _ in range(n)]
for i in range(n):
    d[i][i] = 0
for i in range(e):
    u, v, c = map(int, stdin.readline().split())
    d[u][v] = c
for k in range(n):
    for i in range(n):
        for j in range(n):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]
for i in range(n):
    if d[i][i] < 0:
        print("NEGATIVE CYCLE")
        exit(0)
for di in d:
    print(' '.join(('INF' if isinf(dij) else str(dij) for dij in di)))

Solution (Python):
from sys import stdin
from math import isinf
n, e = map(int, stdin.readline().split())
d = [[float('inf')] * n for _ in range(n)]
for i in range(n):
    d[i][i] = 0
for i in range(e):
    u, v, c = map(int, stdin.readline().split())
    d[u][v] = c
for k in range(n):
    for i in range(n):
        if d[i][k] == float('inf'): continue
        for j in range(n):
            if d[k][j] == float('inf'): continue
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]
for i in range(n):
    if d[i][i] < 0:
        print("NEGATIVE CYCLE")
        exit(0)
for di in d:
    print(' '.join(('INF' if isinf(dij) else str(dij) for dij in di)))

Solution (Python):
from sys import stdin
from math import isinf
n, e = map(int, stdin.readline().split())
d = [[float('inf')] * n for _ in range(n)]
for i in range(n):
    d[i][i] = 0
for i in range(e):
    u, v, c = map(int, stdin.readline().split())
    d[u][v] = c
for k in range(n):
    for i in range(n):
        for j in range(n):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]
for i in range(n):
    if d[i][i] < 0:
        print("NEGATIVE CYCLE")
        exit(0)
for di in d:
    print(' '.join(('INF' if isinf(dij) else str(dij) for dij in di)))

Solution (Python):
from sys import stdin
from math import isinf
import itertools
n, e = map(int, stdin.readline().split())
d = [[float('inf')] * n for _ in range(n)]
for i in range(n):
    d[i][i] = 0
for i in range(e):
    u, v, c = map(int, stdin.readline().split())
    d[u][v] = c
for k, i, j in itertools.product(range(n), repeat=3):
    if d[i][j] > d[i][k] + d[k][j]:
        d[i][j] = d[i][k] + d[k][j]
for i in range(n):
    if d[i][i] < 0:
        print("NEGATIVE CYCLE")
        exit(0)
for di in d:
    print(' '.join(('INF' if isinf(dij) else str(dij) for dij in di)))

Solution (Python):
from sys import stdin
from math import isinf
import itertools
n, e = map(int, stdin.readline().split())
d = [[float('inf')] * n for _ in range(n)]
for i in range(n):
    d[i][i] = 0
for i in range(e):
    u, v, c = map(int, stdin.readline().split())
    d[u][v] = c
for k, i, j in itertools.product(range(n), repeat=3):
    if d[i][j] > d[i][k] + d[k][j]:
        d[i][j] = d[i][k] + d[k][j]
for i in range(n):
    if d[i][i] < 0:
        print("NEGATIVE CYCLE")
        exit(0)
for di in d:
    print(*['INF' if isinf(dij) else str(dij) for dij in di])

Solution (Python):
import math


def main():
    nvertices, nedges = map(int, input().split())
    INF = float('inf')
    D1 = [[0 if i == j else INF for i in range(nvertices)]
          for j in range(nvertices)]
    for i in range(nedges):
        u, v, w = map(int, input().split())
        D1[u][v] = w

    for k in range(nvertices):
        D2 = [[0] * nvertices for i in range(nvertices)]
        for i in range(nvertices):
            for j in range(nvertices):
                D2[i][j] = min(D1[i][j], D1[i][k] + D1[k][j])
        D1 = D2

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

    for D in D1:
        print(" ".join(map(lambda e: "INF" if math.isinf(e) else str(e), D)))


main()

Solution (Python):
from collections import defaultdict

INF = 999999999999999999999

def bellman_ford(G, n):
  d = {}
  for i in range(n):
    d[i] = {}
    for j in range(n):
      if i in G and j in G[i]:
        d[i][j] = G[i][j]
      else:
        d[i][j] = INF
    d[i][i] = 0
  for k in range(n):
    for i in range(n):
      for j in range(n):
        if d[i][k] == INF or d[k][j] == INF:
          continue
        if d[i][j] > d[i][k] + d[k][j]:
          d[i][j] = d[i][k] + d[k][j]
  return d

G = {}

n, m = [int(v) for v in input().strip().split(' ')]
for i in range(n):
  G[i] = {}
for _ in range(m):
  s, t, c = [int(v) for v in input().strip().split(' ')]
  G[s][t] = c

d = bellman_ford(G, n)

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

for i in range(n):
  print(" ".join([str(d[i][j]) if d[i][j] != INF else "INF" for j in range(n)]))

Solution (Python):
def main():
    nvertices, nedges = map(int, input().split())
    INF = float('inf')
    W = [[0 if i == j else INF for i in range(nvertices)] for j in range(nvertices)]
    for i in range(nedges):
        u, v, w = map(int, input().split())
        W[u][v] = w

    for k in range(nvertices):
        for i in range(nvertices):
            for j in range(nvertices):
                W[i][j] = min(W[i][j], W[i][k] + W[k][j])

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

    for lst in W:
        print(" ".join(map(lambda e: str(e) if e < INF else "INF", lst)))


main()

Solution (Python):
import random


def main():
    nvertices, nedges = map(int, input().split())
    INF = float('inf')
    W = [[0 if i == j else INF for i in range(nvertices)] for j in range(nvertices)]
    for i in range(nedges):
        u, v, w = map(int, input().split())
        W[u][v] = w

    lst = [i for i in range(nvertices)]
    random.shuffle(lst)
    for k in lst:
        for i in range(nvertices):
            for j in range(nvertices):
                W[i][j] = min(W[i][j], W[i][k] + W[k][j])

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

    for lst in W:
        print(" ".join(map(lambda e: str(e) if e < INF else "INF", lst)))


main()

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 i in range(V):
        for j in range(V):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]
            
for i in range(V):
    if d[i][i] < 0:
        print('NEGATIVE CYCLE')
        exit()

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

Solution (Python):

"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_C&lang=jp
"""
import sys


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


def main(args):
    V, E = [int(x) for x in 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 = [int(x) for x in input().split(' ')]
        dp[f][t] = d
    
    warshallFloyd(V, dp)

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


if __name__ == '__main__':
    main(sys.argv[1:])

Solution (Python):

def inpl(): return tuple(map(int, input().split()))

INF = float("inf")

V, E = inpl()
adj = [[] for _ in range(V)]
D = [[INF]*V for _ in range(V)]

for _ in range(E):
    s, t, d = inpl()
    D[s][t] = d
    D[t][t] = d

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

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

for v in range(V):
    if D[v][v] < 0:
        print("NEGATIVE CYCLE")
        break
else:
    for d in range(V):
        print(" ".join(map(str, D[d])).replace("inf", "INF"))

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

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

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

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

Solution (Python):
from collections import defaultdict
vertices, edges = (int(n) for n in input().split(" "))
connect = defaultdict(list)
cost_dp = [[float("inf") if n != m else 0 for n in range(vertices)] for m in range(vertices)]
for e in range(edges):
    v1, v2, weight = (int(n) for n in input().split(" "))
    connect[v1].append([v2,weight])
    connect[v2].append([v1,weight])
    cost_dp[v1][v2] = weight
for neg in range(2):
    updated = 0
    for t in range(vertices):
        for i in range(vertices):
            for k in range(vertices):
                if cost_dp[i][k] > cost_dp[i][t] + cost_dp[t][k]:
                    updated = 1
                    cost_dp[i][k] = cost_dp[i][t] + cost_dp[t][k]
if neg == 1 and updated:
    print("NEGATIVE CYCLE")
else:
    for ve in range(vertices):
        ans = ["INF" if n == float("inf") else n for n in cost_dp[ve]]
        print(*ans)

Solution (Python):
vertices, edges = (int(n) for n in input().split(" "))
cost_dp = [[float("inf") if n != m else 0 for n in range(vertices)] for m in range(vertices)]
for e in range(edges):
    v1, v2, weight = (int(n) for n in input().split(" "))
    cost_dp[v1][v2] = weight
for neg in range(2):
    updated = 0
    for t in range(vertices):
        for i in range(vertices):
            for k in range(vertices):
                if cost_dp[i][k] > cost_dp[i][t] + cost_dp[t][k]:
                    updated = 1
                    cost_dp[i][k] = cost_dp[i][t] + cost_dp[t][k]
if neg == 1 and updated:
    print("NEGATIVE CYCLE")
else:
    for ve in range(vertices):
        ans = ["INF" if n == float("inf") else n for n in cost_dp[ve]]
        print(*ans)

Solution (Python):
def main():
    INF = int(1e12)
    G = [[0 for i in range(101)] for j in range(101)];

    v, e = map(int, raw_input().split())

    for i in range(v):
        for j in range(v):
            if i == j:
                G[i][j] = 0
            else:
                G[i][j] = INF

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

    for k in range(v):
        for i in range(v):
            for j in range(v):
                if G[i][k] != INF and G[k][j] != INF:
                    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 0

    for i in range(v):
        ans = []

        for j in range(v):
            if G[i][j] == INF:
                ans.append("INF")
            else:
                ans.append(G[i][j])

        print " ".join(map(str, ans))

main()

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 i in range(V):
        for j in range(V):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]

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

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

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

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

    diag = [adj[i][i]==abs(adj[i][i]) for i in xrange(V)]
    if False in diag:
        print "NEGATIVE CYCLE"
    else:
        for item in adj:
            for i in xrange(V):
                d = item[i]
                if i!=V-1:
                    if d==float("inf"):
                        print "INF",
                    else:
                        print d,
                else:                    
                    if d==float("inf"):
                        print "INF"
                    else:
                        print d

if __name__ == "__main__":
    main()

Solution (Python):



if __name__ == '__main__':

    n, m = [int(s) for s in input().split()]
    A = [[float("inf") for j in range(n)] for i 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

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

    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):
            print(" ".join(map(lambda x: str(x).upper(), A[i])))

Solution (Python):

def inpl(): return tuple(map(int, input().split()))
 
INF = float("inf")
 
V, E = inpl()
adj = [[] for _ in range(V)]
D = [[INF]*V for _ in range(V)]
 
for _ in range(E):
    s, t, d = inpl()
    D[s][t] = d
 
for v in range(V):
    D[v][v] = 0 

def WarshallFloyd(G):
    V = len(G)
    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

D = WarshallFloyd(D)

for v in range(V):
    if D[v][v] < 0:
        print("NEGATIVE CYCLE")
        break
else:
    for d in range(V):
        print(" ".join(map(str, D[d])).replace("inf", "INF"))

Solution (Python):
import queue
import math


def warshall(graph, n):
    for i in range(n):
        graph[i][i] = 0

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

    return graph


def main():
    n, m = map(int, input().split())
    graph = [[float('inf') for _ in range(n)] for _ in range(n)]

    for _ in range(m):
        data = list(map(int, input().split()))

        graph[data[0]][data[1]] = data[2]

    dist = warshall(graph, n)

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

    for i in range(n):
        for j in range(n):

            if j == 0:
                print(dist[i][j] if dist[i][j] != float('inf') else 'INF', end="")
            else:
                print(' {}'.format(dist[i][j] if dist[i][j] != float('inf') else 'INF'), end="")

        print()

    return


if __name__ == '__main__':
    main()

Solution (Python):
def floyd():
    global d
    global INF
    for k in range(n):
        for i in range(n):
            if (d[i][k] == INF):
                continue
            for j in range(n):
                if (d[k][j] == INF):
                    continue
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);


n,q=[int(x) for x in input().split()]
maxx = 110
INF = 1<< 48
d=[[INF for j in range(n+2)] for i in range(n+2)]

for i in range(n):
    d[i][i] =0
            
for i in range(q):    
    s=[int(x) for x in input().split()]
    d[s[0]][s[1]]=s[2]
    
floyd()

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

if (negative):
    print("NEGATIVE CYCLE");
else :
    for i in range(n): 
        for j in range(n):
            if (d[i][j] == INF):
                if j==n-1:print("INF")
                else: print("INF",end=' ')
            else:
                if j!=n-1:print("%d"%(d[i][j]),end=' ')
                else: print("%d"%(d[i][j]))

Solution (Python):
"""
Warshall-Floyd
"""

INF = 10 ** 20

v_num, e_num = map(int, input().split())
dist_lst = [[INF] * v_num for _ in range(v_num)]
negative_cycle_flag = False
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

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

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

def warchall_floyd():
    global A
    for k in range(V):
        for i in range(V):
            if A[i][k] == float('inf'): continue
            for j in range(V):
                if A[k][j] == float('inf'): continue
                A[i][j] = min(A[i][j], A[i][k] + A[k][j])
                if i == j and A[i][i] < 0: return False
    return True

if warchall_floyd():
    for i in range(V):
        print(' '.join([str(x) if x != float('inf') else 'INF' for x in A[i]]))
else:
    print('NEGATIVE CYCLE')

Solution (Python):
import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array





sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = il()
    graph = [[INF] * N for _ in range(N)]
    for _ in range(M):
        s, t, c = il()
        graph[s][t] = c
    for n in range(N):
        graph[n][n] = 0

    
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if graph[i][k] == INF or graph[k][j] == INF: continue
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

    
    ret = []
    for n in range(N):
        if graph[n][n] < 0:
            
            
            print('NEGATIVE CYCLE')
            exit()
        tmp = []
        for d in graph[n]:
            if d == INF:
                tmp.append('INF')
            else:
                tmp.append(d)
        ret.append(tmp)
    else:
        for r in ret:
            print(*r)


if __name__ == '__main__':
    main()

Solution (Python):
V,E = map(int,input().split())
cost_matrix = [[float('inf')]*V for _ in range(V)]
for i in range(V):
    cost_matrix[i][i] = 0
for i in range(E):
    start,end,cost = map(int,input().split())
    cost_matrix[start][end] = cost
for stop in range(V):
    for start in range(V):
        for end in range(V): 
            cost_matrix[start][end] = min(cost_matrix[start][end],cost_matrix[start][stop]+cost_matrix[stop][end])
is_negative = False
for start in range(V):
    for end in range(V):
        if cost_matrix[start][end] < 0 and start == end:
            is_negative = True
        elif cost_matrix[start][end] == float('inf'):
            cost_matrix[start][end] = 'INF'
if is_negative:
    print('NEGATIVE CYCLE')
else:
    for start in range(V):
        res = list(map(str,cost_matrix[start]))
        print(' '.join(res))

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


INFTY = 2 ** 40
lines = stdin.readlines()
v, e = list(map(int, lines[0].split()))

A = [[INFTY] * v for i in range(v)]

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

for i in range(e):
    s, t, d = list(map(int, lines[i+1].split()))
    A[s][t] = d

for k in range(v):
    for i in range(v):
        if A[i][k] == INFTY:
            continue
        for j in range(v):
            if A[k][j] == INFTY:
                continue
            a = A[i][j]
            b = A[i][k] + A[k][j]
            if a > b:
                A[i][j] = b

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


for i in range(v):
    for j in range(v):
        if j < (v-1):
            if A[i][j] == INFTY:
                print('INF', end=' ')
            else:
                print(A[i][j], end=' ')
        else:
            if A[i][j] >= INFTY:
                print('INF')
            else:
                print(A[i][j])

Solution (Python):
INF = 10 ** 20
V, E = map(int, input().split())
graph = [[INF] * 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 k in range(V):
  for i in range(V):
    if graph[i][k] == INF:
      continue
    for j in range(V):
      if graph[k][j] == INF:
        continue
      graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

negative = 0
for i in range(V):
    if graph[i][i] < 0:
      negative = 1
      break

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

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

inf = float("inf")


edges = [[inf]*v for _ in range(v)]
for _ in range(e):
    s, t, d = map(int, input().split())
    edges[s][t] = d

for w in range(v):
    edges[w][w] = 0

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


if any(edges[i][i] < 0 for i in range(v)):
    print("NEGATIVE CYCLE")
else:
    for x in edges:
        x = ["INF" if y == inf else str(y) for y in x]
        print(" ".join(x))

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, 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] != float("INF") and D[k][j] != float("INF"):
                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])