def main():

    nvertices, nedges = list(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 = list(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([str(e) if e < INF else "INF" for e in lst])))





main()
import math





def main():

    nvertices, nedges = list(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 = list(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(["INF" if math.isinf(e) else str(e) for e in D])))





main()
def main():
    nvertices, nedges = list(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 = list(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([str(e) if e < INF else "INF" for e in lst])))


main()

import math


def main():
    nvertices, nedges = list(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 = list(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(["INF" if math.isinf(e) else str(e) for e in D])))


main()

+import math + + -    D1 = [[INF for i in range(nvertices)] for i in range(nvertices)] +    D1 = [[0 if i == j else INF for i in range(nvertices)] for j in range(nvertices)] -        s, t, d = list(map(int, input().split())) -        D1[s][t] = d -    for i in range(nvertices): -        D1[i][i] = 0 +        u, v, w = list(map(int, input().split())) +        D1[u][v] = w -        D2 = [[INF for i in range(nvertices)] for i in range(nvertices)] +        D2 = [[0] * nvertices for i in range(nvertices)] -    for i in range(nvertices): -        if D1[i][i] < 0: +    for v in range(nvertices): +        if D1[v][v] < 0: -    for lst in D1: -        print((" ".join([str(e) if e < INF else "INF" for e in lst]))) +    for D in D1: +        print((" ".join(["INF" if math.isinf(e) else str(e) for e in D])))