from sys import stdin

from math import isinf

n, e = list(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 = list(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))))
from sys import stdin

from math import isinf

n, e = list(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 = list(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))))
from sys import stdin
from math import isinf

n, e = list(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 = list(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))))

from sys import stdin
from math import isinf

n, e = list(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 = list(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))))

-        if d[i][k] == float("inf"): -            continue -            if d[k][j] == float("inf"): -                continue