import sys

readline = sys.stdin.readline



V, E = list(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 = list(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)))
import sys



def warshall_floyd(v_count, matrix):

    for i in range(v_count):

        for j in range(v_count):

            c2 = matrix[j][i]

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

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





V, E = list(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 (list(map(int, l.split())) for l in sys.stdin):

    matrix[s][t] = d

warshall_floyd(V, matrix)

if has_negative_cycle(matrix):

    print("NEGATIVE CYCLE")

else:

    for row in matrix:

        print((" ".join([str(n) if n!=inf else "INF" for n in row])))

import sys

readline = sys.stdin.readline
V, E = list(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 = list(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)))

import sys


def warshall_floyd(v_count, matrix):
    for i in range(v_count):
        for j in range(v_count):
            c2 = matrix[j][i]
            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) -> bool:
    return any(row[i] < 0 for i, row in enumerate(a))


V, E = list(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 (list(map(int, l.split())) for l in sys.stdin):
    matrix[s][t] = d
warshall_floyd(V, matrix)
if has_negative_cycle(matrix):
    print("NEGATIVE CYCLE")
else:
    for row in matrix:
        print((" ".join([str(n) if n != inf else "INF" for n in row])))

-readline = sys.stdin.readline -V, E = list(map(int, readline().split())) + +def warshall_floyd(v_count, matrix): +    for i in range(v_count): +        for j in range(v_count): +            c2 = matrix[j][i] +            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) -> bool: +    return any(row[i] < 0 for i, row in enumerate(a)) + + +V, E = list(map(int, input().split())) -vertices = [[inf if i != j else 0 for j in range(V)] for i in range(V)] -for _ in [None] * E: -    s, t, d = list(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])) +matrix = [[inf] * V for _ in [0] * V] +for i in range(V): +    matrix[i][i] = 0 +for s, t, d in (list(map(int, l.split())) for l in sys.stdin): +    matrix[s][t] = d +warshall_floyd(V, matrix) +if has_negative_cycle(matrix): +    print("NEGATIVE CYCLE") -    print(("\n".join(ans))) +    for row in matrix: +        print((" ".join([str(n) if n != inf else "INF" for n in row])))