import sys



def warshall_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 zip(list(range(v_count)), 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



def warshall_floyd(v_count: int, matrix: list) -> list:

    """ ワーシャルフロイド

    :param v_count: 頂点数

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

    return matrix





def has_negative_cycle(matrix: list) -> bool:

    """ 負閉路チェック

    :param matrix: 隣接行列(ワーシャルフロイドの結果)

    """

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





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


def warshall_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 zip(list(range(v_count)), 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


def warshall_floyd(v_count: int, matrix: list) -> list:
    """ワーシャルフロイド
    :param v_count: 頂点数
    :param 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
    return matrix


def has_negative_cycle(matrix: list) -> bool:
    """負閉路チェック
    :param matrix: 隣接行列(ワーシャルフロイドの結果)
    """
    return any(row[i] < 0 for i, row in enumerate(matrix))


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

-def warshall_floyd(v_count, matrix): +def warshall_floyd(v_count: int, matrix: list) -> list: +    """ワーシャルフロイド +    :param v_count: 頂点数 +    :param matrix: 隣接行列 +    """ -        for j, c2 in enumerate(matrix[j][i] for j in range(v_count)): -            for k, c1, c3 in zip(list(range(v_count)), matrix[j], matrix[i]): +        for j, c2 in enumerate(row[i] for row in matrix): +            for k, (c1, c3) in enumerate(zip(matrix[j], matrix[i])): -def has_negative_cycle(a) -> bool: -    return any(row[i] < 0 for i, row in enumerate(a)) +def has_negative_cycle(matrix: list) -> bool: +    """負閉路チェック +    :param matrix: 隣接行列(ワーシャルフロイドの結果) +    """ +    return any(row[i] < 0 for i, row in enumerate(matrix))