INF = 1<<31

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

l = [[INF]*V for i in range(V)]

for i in range(E):

    s, t, d = list(map(int, input().split()))

    l[s][t] = d

for k in range(V):

    for i in range(V):

        for j in range(V):

            if l[i][k] != INF and l[k][j] != INF:

                l[i][j] = min(l[i][j], l[i][k] + l[k][j])

for i in range(V):

    if l[i][i] < 0:

        print("NEGATIVE CYCLE")

        break

    l[i][i] = 0

else:

    for r in l:

        for i in range(V):

            if r[i] == INF: r[i] = "INF"

        print(" ".join(map(str, r)))
INF = float("inf")

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

l = [[INF]*V for i in range(V)]

for i in range(E):

    s, t, d = list(map(int, input().split()))

    l[s][t] = d

for k in range(V):

    for i in range(V):

        for j in range(V):

            l[i][j] = min(l[i][j], l[i][k] + l[k][j])

for i in range(V):

    if l[i][i] < 0:

        print("NEGATIVE CYCLE")

        break

    l[i][i] = 0

else:

    for r in l:

        for i in range(V):

            if r[i] == INF: r[i] = "INF"

        print(" ".join(map(str, r)))
INF = 1 << 31
V, E = list(map(int, input().split()))
l = [[INF] * V for i in range(V)]
for i in range(E):
    s, t, d = list(map(int, input().split()))
    l[s][t] = d
for k in range(V):
    for i in range(V):
        for j in range(V):
            if l[i][k] != INF and l[k][j] != INF:
                l[i][j] = min(l[i][j], l[i][k] + l[k][j])
for i in range(V):
    if l[i][i] < 0:
        print("NEGATIVE CYCLE")
        break
    l[i][i] = 0
else:
    for r in l:
        for i in range(V):
            if r[i] == INF:
                r[i] = "INF"
        print(" ".join(map(str, r)))

INF = float("inf")
V, E = list(map(int, input().split()))
l = [[INF] * V for i in range(V)]
for i in range(E):
    s, t, d = list(map(int, input().split()))
    l[s][t] = d
for k in range(V):
    for i in range(V):
        for j in range(V):
            l[i][j] = min(l[i][j], l[i][k] + l[k][j])
for i in range(V):
    if l[i][i] < 0:
        print("NEGATIVE CYCLE")
        break
    l[i][i] = 0
else:
    for r in l:
        for i in range(V):
            if r[i] == INF:
                r[i] = "INF"
        print(" ".join(map(str, r)))

-INF = 1 << 31 +INF = float("inf") -            if l[i][k] != INF and l[k][j] != INF: -                l[i][j] = min(l[i][j], l[i][k] + l[k][j]) +            l[i][j] = min(l[i][j], l[i][k] + l[k][j])