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

def floyd_warshall(dist: "Array[Array[int]]") -> None:
    """
    Compute the shortest paths of all pairs.
    """
    V = len(dist)
    for i in range(V):  
        for j, c2 in enumerate(dist[j][i] for j in range(V)):  
            for k, (c1, c3) in enumerate(zip(dist[j], dist[i])):  
                if c2 + c3 < c1:
                    dist[j][k] = c2 + c3


def detect_negative_cycle(dist: "Array[Array[int]]") -> bool:
    return any(d[i] < 0 for i, d in enumerate(dist))


def main():
    N, M, *E = map(int, open(0).read().split())
    dist = [[float("inf")] * N for _ in range(N)]
    for i in range(N):
        dist[i][i] = 0
    for v, u, c in zip(*[iter(E)] * 3):
        dist[v][u] = c
    floyd_warshall(dist)
    if detect_negative_cycle(dist):
        print("NEGATIVE CYCLE")
    else:
        for d in dist:
            cur = [i if i != float("inf") else "INF" for i in d]
            print(" ".join(map(str, cur)))


if __name__ == "__main__":
    main()

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


def main():
    V, E = map(int, input().split())
    graph = [[INF]*V for _ in range(V)]
    for _ in range(E):
        s, t, d = map(int, input().split())
        graph[s][t] = d
    for i in range(V):
        graph[i][i] = 0
    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])
    flag = False
    for i in range(V):
        if graph[i][i] < 0:
            flag = True
            break
    if flag:
        print('NEGATIVE CYCLE')
    else:
        for A in graph:
            if A[0] == INF:
                print('INF', end='')
            else:
                print(A[0], end='')
            for i in range(1, V):
                if A[i] == INF:
                    print(' INF', end='')
                else:
                    print(' {}'.format(A[i]), end='')
            print()


if __name__ == '__main__': main()

Solution (Python):
lv, le = map(int, input().split())
inf = 1e10

d = [[inf] * lv for _ in range(lv)]
for v in range(lv):
    d[v][v] = 0
for _ in range(le):
    s, t, c = map(int, input().split())
    d[s][t] = c

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

isneg = False
for v in range(lv):
    if d[v][v] < 0:
        isneg = True
if isneg:
    print('NEGATIVE CYCLE')
else:
    for i in range(lv):
        print(' '.join([str(d[i][j]) if d[i][j] < inf else 'INF' for j in range(lv)]))

Solution (Python):
INFTY = 10**13
def floyd():
    for k in range(n):
        for i in range(n):
            if d[i][k] == INFTY:
                continue
            for j in range(n):
                if d[k][j] == INFTY:
                    continue
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])

n, e = map(int, input().split())
d = [[0 if i == j else INFTY for j in range(n)]for i in range(n)]

for i in range(e):
    u, v, c = map(int, input().split())
    d[u][v] = c

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 j:
                print(" ", end='')
            if d[i][j] == INFTY:
                print("INF", end='')
            else:
                print(d[i][j], end='')
        print()

Solution (Python):
import sys

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

Edge = [[] for _ in range(v)]

for i in range(e):
    inpt = list(map(int, input().split( )))
    Edge[inpt[0]].append(inpt[1:])

inf = 10**12


dp = [[inf for _ in range(v)] for __ in range(v)]
for i in range(v):
    for ed in Edge[i]:
        dp[i][ed[0]] = ed[1]
for i in range(v):
    dp[i][i] = 0
"""
・for k,for i, for jの順。for i,j,kだと別物
・dpはkによらず使い回しでよい
"""
for k in range(v):
    for j in range(v):
        for i 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")
        sys.exit()

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

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

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

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

Solution (Python):
import sys


if __name__ == "__main__":
    V, E = map(lambda x: int(x), input().split())

    dists = [[sys.maxsize for _ in range(V)] for _ in range(V)]
    for i in range(V):
        dists[i][i] = 0

    for _ in range(E):
        s, t, dist = map(lambda x: int(x), input().split())
        if dist < dists[s][t]:
            dists[s][t] = dist

    for t in range(V):
        for s in range(V):
            if sys.maxsize == dists[s][t]:
                continue
            for goal in range(V):
                if sys.maxsize == dists[t][goal]:
                    continue
                if dists[s][t] + dists[t][goal] < dists[s][goal]:
                    dists[s][goal] = dists[s][t] + dists[t][goal]

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

    for dist in dists:
        print(" ".join([str(elem) if sys.maxsize != elem else "INF" for elem in dist]))

Solution (Python):
class WarshallFloyd():
    def __init__(self, N):
        self.N = N
        self.d = [[float("inf") for i in range(N)]
                  for i in range(N)]  

    def add(self, u, v, c, directed=False):
        """
        0-indexedであることに注意
        u = from, v = to, c = cost
        directed = Trueなら、有向グラフである
        """
        if directed is False:
            self.d[u][v] = c
            self.d[v][u] = c
        else:
            self.d[u][v] = c

    def WarshallFloyd_search(self):
        
        
        
        for k in range(self.N):
            for i in range(self.N):
                for j in range(self.N):
                    self.d[i][j] = min(
                        self.d[i][j], self.d[i][k] + self.d[k][j])
        hasNegativeCycle = False
        for i in range(self.N):
            if self.d[i][i] < 0:
                hasNegativeCycle = True
                break
        for i in range(self.N):
            self.d[i][i] = 0
        return hasNegativeCycle, self.d


V, E = map(int, input().split())
graph = WarshallFloyd(V)
for i in range(E):
    s, t, d = map(int, input().split())
    graph.add(s, t, d, True)

hasNegativecycle, dist = graph.WarshallFloyd_search()

if hasNegativecycle:
    print("NEGATIVE CYCLE")
    quit()
for row in range(V):
    if dist[row][0] == float('inf'):
        print("INF", end="")
    else:
        print("%d" % (dist[row][0]), end="")
    for col in range(1, V):
        if dist[row][col] == float('inf'):
            print(" INF", end="")
        else:
            print(" %d" % (dist[row][col]), end="")
    print()

Solution (Python):

import string
import sys
from itertools import chain, dropwhile, takewhile

INF = float("inf")


def read(
    *shape, f=int, it=chain.from_iterable(sys.stdin), whitespaces=set(string.whitespace)
):
    def read_word():
        w = lambda c: c in whitespaces
        nw = lambda c: c not in whitespaces
        return f("".join(takewhile(nw, dropwhile(w, it))))

    if not shape:
        return read_word()
    elif len(shape) == 1:
        return [read_word() for _ in range(shape[0])]
    elif len(shape) == 2:
        return [[read_word() for _ in range(shape[1])] for _ in range(shape[0])]


def readi(*shape):
    return read(*shape)


def readi1(*shape):
    return [i - 1 for i in readi(*shape)]


def readf(*shape):
    return read(*shape, f=float)


def reads(*shape):
    return read(*shape, f=str)


def arr(*shape, fill_value=0):
    if len(shape) == 1:
        return [fill_value] * shape[0]
    elif len(shape) == 2:
        return [[fill_value] * shape[1] for _ in range(shape[0])]


def dbg(**kwargs):
    print(
        ", ".join("{} = {}".format(k, repr(v)) for k, v in kwargs.items()),
        file=sys.stderr,
    )


def main():
    V, E = readi(2)
    G = arr(V, V, fill_value=INF)
    for i in range(V):
        G[i][i] = 0
    for _ in range(E):
        s, t, d = readi(3)
        G[s][t] = d

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

    for k in range(V):
        for i in range(V):
            for j in range(V):
                if G[i][j] > G[i][k] + G[k][j]:
                    print("NEGATIVE CYCLE")
                    return

    for i in range(V):
        print(" ".join(map(lambda n: "INF" if n == INF else str(n), G[i])))


if __name__ == "__main__":
    main()

Solution (Python):

"""
Created on Sun Jun 30 22:06:02 2019
WarshallFloyd_search
@author: maezawa
"""
import collections


class WarshallFloyd():
    def __init__(self, N):
        self.edges = []
        self.N = N
        self.d = [[float("inf") for i in range(N)]
                  for i in range(N)]  

    def add(self, u, v, c, directed=False):
        """
        0-indexedであることに注意
        u = from, v = to, c = cost
        directed = Trueなら、有向グラフである
        """
        if directed:
            self.d[u][v] = c
        else:
            self.d[u][v] = c
            self.d[v][u] = c
        if directed:
            self.edges.append([u, v, c])
        else:
            self.edges.append([u, v, c])
            self.edges.append([v, u, c])


    def WarshallFloyd_search(self):
        
        
        for k in range(self.N):
            for i in range(self.N):
                for j in range(self.N):
                    self.d[i][j] = min(
                        self.d[i][j], self.d[i][k] + self.d[k][j])
        for i in range(self.N):
            self.d[i][i] = 0
        return self.d

    def BellmanFord_negative_bool(self, numNodes, start, zero_indexed=False):
        
        dd = collections.defaultdict(lambda: float('inf'))
        dd[0] = 0
        numEdges = len(self.edges)
        for i in range(numNodes):
            for j in range(numEdges):
                e = self.edges[j]
                if dd[e[1]] > dd[e[0]] + e[2]:
                    dd[e[1]] = dd[e[0]] + e[2]
                    if i == numNodes-1:
                        return True
        return False
    


        
num_v, num_edges = list(map(int, input().split()))      
graph = WarshallFloyd(num_v)

for i in range(num_edges):
    u,v,w = list(map(int, input().split()))
    graph.add(u, v, w, directed=True)

if graph.BellmanFord_negative_bool(num_v, 0, zero_indexed=True):
    print('NEGATIVE CYCLE')
else:
    result = graph.WarshallFloyd_search()
    for i in range(num_v):
        s = []
        for j in range(num_v):
            if result[i][j] == float("inf"):
                s.append('INF')
            else:
                s.append(str(result[i][j]))
        print(' '.join(s))

Solution (Python):




n,e = [int(i) for i in input().split()]

"""隣接行列の初期化"""
INF = float("inf")
dist = [[float("inf")]*n for _ in [0]*n]
for i in range(n):
    dist[i][i] = 0

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

def Floyd_Warshall(dist): 
    """
    Floyd_Warshall 
    dist: 隣接行列（破壊される)
    
    
    
    """
    num_of_vertices = len(dist)
    for k in range(num_of_vertices):
        for i, c2 in enumerate(dj[k] for dj in dist):
            for j, (c1, c3) in enumerate(zip(dist[i], dist[k])):
                if c1 > c2+c3:
                    dist[i][j] = c2+c3

Floyd_Warshall(dist)

def has_negative_cycle(dist) -> bool:
    return any(row[i] < 0 for i, row in enumerate(dist))
 
if has_negative_cycle(dist):
    print("NEGATIVE CYCLE")
    exit()
else:
    for row in dist:
        print(" ".join(map(lambda n: str(n) if n!=INF else "INF", row)))

Solution (Python):
v, e = map(int, input().split())
inf = 2**32
dp = [[inf for _ in range(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):
        if dp[i][k] >= inf:
            continue
        for j in range(v):
            if dp[k][j] >= inf:
                continue
            dp[i][j] = min([dp[i][j], dp[i][k]+dp[k][j]])

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

if negative:
    print("NEGATIVE CYCLE")
else:
    for i in range(v):
        ans = []
        for j in range(v):
            if dp[i][j] >= inf:
                ans.append("INF")
            else:
                ans.append(str(dp[i][j]))
        print(" ".join(ans))

Solution (Python):
import sys
from math import isinf
def warshall_floyd(v_count: int):
    """ ワーシャルフロイド　(user:htkb)
    :param v_count: 頂点数
    :param matrix:  隣接行列(到達不能はfloat("inf"))
    """
    
    
    global matrix
    for i in range(v_count):
        for j, c2 in enumerate(row[i] for row in matrix):
            for k, (c1, c3) in enumerate(zip(matrix[j], matrix[i])):
                if c1 > c2+c3:
                    matrix[j][k] = c2+c3 

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

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

    warshall_floyd(V)
    for i in range(V):
        if matrix[i][i] < 0:
            print("NEGATIVE CYCLE")
            sys.exit()
    for mi in matrix:
        print(' '.join( ('INF' if isinf(dij) else str(dij) for dij in mi)))

Solution (Python):
INF = 2e10


def main():
    n, m = map(int, input().split())

    mat = [[INF] * n for i in range(n)]
    for i in range(n):
        mat[i][i] = 0
    for i in range(m):
        s, t, c = map(int, input().split())
        mat[s][t] = c

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

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

    for i in range(n):
        for j in range(n):
            if j > 0:
                print(' ', end="")
            if mat[i][j] == INF:
                print('INF', end="")
            else:
                print(mat[i][j], end="")
        print()


main()

Solution (Python):
V,E = map(int,input().strip().split())
K = [["INF" for _ in range(V)] for _ in range(V)]
for i in range(V):
    K[i][i] = 0
for t in range(E):
    S,T,D = map(int,input().strip().split())
    K[S][T] = D
for k in range(V):
    for i in range(V):
        for j in range(V):
            if (K[i][k] != "INF") and (K[k][j] != "INF"):
                if K[i][j] == "INF" or K[i][j] > K[i][k] + K[k][j]:
                    K[i][j] = K[i][k] + K[k][j]
b = 0
for t in range(V):
    if K[t][t] != "INF" and K[t][t] < 0:
        print("NEGATIVE CYCLE")
        b += 1
        break
if b == 0:
    for i in range(V):
        print(" ".join(map(str,K[i])))

Solution (Python):
def func(V, W):
    for k in range(V):
        for i in range(V):
            w_ik = W[i][k]
            for j, (w_ij, w_kj) in enumerate(zip(W[i], W[k])):
                W[i][j] = min(w_ij, w_ik + w_kj)

V, E = map(int, input().split())
W = [[float("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

func(V, W)

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

for temp in W:
    print(" ".join(list(map(str, temp))).upper())

Solution (Python):
INF = 2000000000


def read_adj_mat():
    nv, ne = [int(x) for x in input().split()]
    A = [[0 if fr == to else INF for fr in range(nv)] for to in range(nv)]
    for _ in range(ne):
        s, t, d = [int(x) for x in input().split()]
        A[s][t] = d
    return A


def get_shortest_paths(D):
    n = len(D)
    for to in range(n):
        for fr in range(n):
            here = D[fr][to]
            if here == INF:
                continue
            for to2 in range(n):
                here2 = D[to][to2]
                if here2 == INF:
                    continue
                D[fr][to2] = min(D[fr][to2], here + here2)


def print_result(D):
    for fr in range(len(D)):
        for to in range(len(D)):
            if to != 0:
                print(" ", end="")
            if D[fr][to] == INF:
                print("INF", end="")
            else:
                print(D[fr][to], end="")
        print()


def main():
    D = read_adj_mat()
    get_shortest_paths(D)
    for d in [D[x][x] for x in range(len(D))]:
        if d < 0:
            print("NEGATIVE CYCLE")
            break
    else:
        print_result(D)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
readline = sys.stdin.readline
writelines = sys.stdout.writelines
write = sys.stdout.write

from collections import deque
from heapq import heappush, heappop

INF = 10**30
def Johnson(G):
    h = [0]*N

    update = 1
    for i in range(N):
        update = 0
        for v in range(N):
            d = h[v]
            for w, c in G[v]:
                if c + d < h[w]:
                    h[w] = d + c
                    update = 1
        if not update:
            break
    else:
        return None

    for v in range(N):
        d = h[v]
        g = G[v]
        for j, (w, c) in enumerate(g):
            g[j] = (w, c + d - h[w])

    D = []
    for i in range(N):
        dst = [INF]*N
        dst[i] = 0
        que = [(0, i)]
        while que:
            cost, v = heappop(que)
            if dst[v] < cost:
                continue
            for w, c in G[v]:
                if cost + c < dst[w]:
                    dst[w] = r = cost + c
                    heappush(que, (r, w))
        v = h[i]
        for j in range(N):
            if dst[j] == INF:
                dst[j] = INF
            else:
                dst[j] -= v - h[j]
        D.append(dst)

    return D


N, M = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
    s, t, d = map(int, input().split())
    G[s].append((t, d))

D = Johnson(G)
if D:
    ans = []
    for i in range(N):
        ans.append(" ".join(str(v) if v < INF else "INF" for v in D[i]))
        ans.append("\n")
    writelines(ans)
else:
    write("NEGATIVE CYCLE\n")

Solution (Python):
def input(f):
    global v, e, s, t, d
     
    v, e = map(int, f.readline().split())
    s = []
    t = []
    d = []
    for _ in range(e):
        s_, t_, d_ = map(int, f.readline().split())
        s.append(s_)
        t.append(t_)
        d.append(d_)
 
import os
 
if os.environ.get('ZEPPELIN_HOME'):
    import networkx as nx
    import matplotlib.pyplot as plt
     
    def visualize():
        G = nx.MultiDiGraph()
        for i in range(v):
            G.add_node(i, node_color='b')
        for i in range(e):
            G.add_edge(s[i], t[i], t=d[i])
 
        plt.figure()
        plt.style.use('seaborn')
        plt.axis("off")
        pos = nx.spring_layout(G)
        nodes = nx.draw_networkx_nodes(G, pos, node_color='w', linewidths=2)
        nodes.set_edgecolor('black')
        nx.draw_networkx_labels(G, pos)
        nx.draw_networkx_edges(G, pos)
 
        edge_labels = dict([((a, b), c['t']) for a, b, c in G.edges(data=True)])
        nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels, label_pos=0.25, font_size=16)
 
        plt.show()
 
if os.environ.get('ZEPPELIN_HOME'):
    with open('/tmp/input1') as f:
        print('Example 
        input(f)
        visualize()
 
if os.environ.get('ZEPPELIN_HOME'):
    with open('/tmp/input2') as f:
        print('Example 
        input(f)
        visualize()
 
if os.environ.get('ZEPPELIN_HOME'):
    with open('/tmp/input3') as f:
        print('Example 
        input(f)
        visualize()
 
import sys
 
 
def init():
    global inf, g
    inf = sys.maxsize
     
    g = [[inf for _ in range(v)] for _ in range(v)]
    for i in range(v):
        g[i][i] = 0
    for i in range(e):
        g[s[i]][t[i]] = d[i]
         
 
def solve():
    init()
     
    for k in range(v):
        for i in range(v):
            for j in range(v):
                if g[i][k] == inf or g[k][j] == inf:
                    continue
                g[i][j] = min([g[i][j], g[i][k] + g[k][j]])
 
    for i in range(v):
        if g[i][i] != 0:
            print('NEGATIVE CYCLE')
            return
         
    for i in range(v):
        for j in range(v):
            if j > 0:
                print(' ', end='')
            if g[i][j] == inf:
                print('INF', end='')
            else:
                print(g[i][j], end='')
        print('')
 
if os.environ.get('ZEPPELIN_HOME'):
    os.environ['INPUT'] = '/tmp/input1'
 
with open(os.environ.get('INPUT') or '/dev/stdin') as f:
    input(f)
    solve()
 
if os.environ.get('ZEPPELIN_HOME'):
    os.environ['INPUT'] = '/tmp/input2'
 
    with open(os.environ.get('INPUT') or '/dev/stdin') as f:
        input(f)
        solve()
 
if os.environ.get('ZEPPELIN_HOME'):
    os.environ['INPUT'] = '/tmp/input3'
 
    with open(os.environ.get('INPUT') or '/dev/stdin') as f:
        input(f)
        solve()

Solution (Python):
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001


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

min_dist = [[BIG_NUM]*V for i in range(V)]

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

for loop in range(E):
    tmp_from,tmp_to,tmp_cost = map(int,input().split())
    if min_dist[tmp_from][tmp_to] > tmp_cost:
        min_dist[tmp_from][tmp_to] = tmp_cost

for mid in range(V):
    for start in range(V):
        if min_dist[start][mid] == BIG_NUM:
            continue
        for goal in range(V):
            if min_dist[mid][goal] == BIG_NUM:
                continue
            if min_dist[start][goal] > min_dist[start][mid]+min_dist[mid][goal]:
                min_dist[start][goal] = min_dist[start][mid]+min_dist[mid][goal]


neg_FLG = False

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


if neg_FLG == True:
    print("NEGATIVE CYCLE")
    sys.exit()

for row in range(V):
    if min_dist[row][0] == BIG_NUM:
        print("INF",end = "")
    else:
        print("%d"%(min_dist[row][0]),end = "")
    for col in range(1,V):
        if(min_dist[row][col] == BIG_NUM):
            print(" INF",end = "")
        else:
            print(" %d"%(min_dist[row][col]),end = "")
    print()

Solution (Python):
import sys

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

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

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

Solution (Python):
from itertools import product
V,E = map(int,input().split())
edges = [tuple() for _ in range(E)]
dist = [[float("inf")]*V for _ in range(V)]
for i in range(V):
    dist[i][i] = 0
for _ in range(E):
    s,t,d = map(int,input().split())
    dist[s][t] = d
for k,i,j in product(range(V),range(V),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])
for i in range(V):
    if dist[i][i] < 0:
        print("NEGATIVE CYCLE")
        exit()
for i in range(V):
    ans = ["INF" if dist[i][j] == float("inf") else dist[i][j] for j in range(V)]
    print(" ".join(map(str, ans)))

Solution (Python):
INFTY = 1 << 32

def floyd(n, d):
    for k in range(n):
        for i in range(n):
            if d[i][k] == INFTY:
                continue
            for j in range(n):
                if d[k][j] == INFTY:
                    continue
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])


if __name__ == '__main__':
    n, e = [int(v) for v in input().split()]
    d = [[INFTY] * n for i in range(n)]
    for i in range(n):
        d[i][i] = 0
    for i in range(e):
        u, v, c = [int(v) for v in input().split()]
        d[u][v] = c

    floyd(n, d)

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

    if negative:
        print('NEGATIVE CYCLE')
    else:
        for i in range(n):
            line = []
            for j in range(n):
                if d[i][j] == INFTY:
                    line.append('INF')
                else:
                    line.append(str(d[i][j]))
            print(' '.join(line))

Solution (Python):



from collections import namedtuple


WEIGHT_MAX = 10 ** 10
WeightedEdge = namedtuple('WeightedEdge', ('src', 'dest', 'weight'))


class Digraph:
    def __init__(self, v):
        self.v = v
        self.edges = [[] for _ in range(v)]

    def add(self, edge):
        self.edges[edge.src].append(edge)

    def adj(self, v):
        return self.edges[v]


def sp_bellmanford(graph, s):
    def relax(edge):
        s, t, w = edge
        if dists[t] > dists[s] + w:
            dists[t] = dists[s] + w
            srcs[t] = s
            _nodes.append(t)

    dists = [WEIGHT_MAX] * graph.v
    dists[s] = 0
    srcs = [-1] * graph.v
    nodes = []

    nodes.append(s)
    for _ in range(graph.v):
        _nodes = []
        for v in nodes:
            for e in graph.adj(v):
                relax(e)
        nodes = _nodes

    if len(nodes) > 0:
        return None
    else:
        return [None if dists[v] == WEIGHT_MAX else dists[v]
                for v in range(graph.v)]


def run():
    v, e = [int(i) for i in input().split()]

    graph = Digraph(v)
    for _ in range(e):
        edge = WeightedEdge(*[int(i) for i in input().split()])
        graph.add(edge)

    paths = []
    for r in range(v):
        ws = sp_bellmanford(graph, r)
        if ws is None:
            print("NEGATIVE CYCLE")
            break
        else:
            paths.append(ws)
    else:
        for ws in paths:
            print(" ".join("INF" if w is None else str(w) for w in ws))


if __name__ == '__main__':
    run()

Solution (Python):
V, E = map(int, input().split())
INF = 10**20
cost = [[INF if x != y else 0 for x in range(V)] for y in range(V)]

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) :
            if cost[i][k] != INF and cost[k][j] != INF :
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])
            
negative_cycle = False 
for i in range(V) :
    if cost[i][i] < 0 :
        negative_cycle = True
        
if negative_cycle == True :
    print("NEGATIVE CYCLE")
else :
    for i in cost :
        i_str = list(map(str, i))
        print(" ".join([x if x != str(INF) else "INF" for x in i_str]))

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