from collections import defaultdict



vertice,edge = list(map(int,input().split(" ")))

cost = [[0 if m == n else float("inf") for n in range(vertice)] for m in range(vertice)]

link = defaultdict(dict)

weight = defaultdict(dict)



for e in range(edge):

    i,j,w = list(map(int,input().split(" ")))

    link[i] = link.get(i,set()) | {j}

    weight[i].update({j:w})



vertice_cnt = 0

while 1:

    if vertice_cnt >= vertice:

        print("NEGATIVE CYCLE")

        break

    update = False

    for source in range(vertice):

        for k,value in list(link.items()):

            for v in value:

                if cost[source][v] > cost[source][k] + weight[k][v]:

                    cost[source][v] = cost[source][k] + weight[k][v]

                    update = True

    if not update:

        for o in range(vertice):



            print((*([n if n != float("INF") else "INF" for n in cost[o]])))

        break

    vertice_cnt += 1
from collections import defaultdict

vertices, edges = (int(n) for n in input().split(" "))

connect = defaultdict(list)

cost_dp = [[float("inf") if n != m else 0 for n in range(vertices)] for m in range(vertices)]

for e in range(edges):

    v1, v2, weight = (int(n) for n in input().split(" "))

    connect[v1].append([v2,weight])

    connect[v2].append([v1,weight])

    cost_dp[v1][v2] = weight

for neg in range(2):

    updated = 0

    for t in range(vertices):

        for i in range(vertices):

            for k in range(vertices):

                if cost_dp[i][k] > cost_dp[i][t] + cost_dp[t][k]:

                    updated = 1

                    cost_dp[i][k] = cost_dp[i][t] + cost_dp[t][k]

if neg == 1 and updated:

    print("NEGATIVE CYCLE")

else:

    for ve in range(vertices):

        ans = ["INF" if n == float("inf") else n for n in cost_dp[ve]]

        print((*ans))
from collections import defaultdict

vertice, edge = list(map(int, input().split(" ")))
cost = [[0 if m == n else float("inf") for n in range(vertice)] for m in range(vertice)]
link = defaultdict(dict)
weight = defaultdict(dict)
for e in range(edge):
    i, j, w = list(map(int, input().split(" ")))
    link[i] = link.get(i, set()) | {j}
    weight[i].update({j: w})
vertice_cnt = 0
while 1:
    if vertice_cnt >= vertice:
        print("NEGATIVE CYCLE")
        break
    update = False
    for source in range(vertice):
        for k, value in list(link.items()):
            for v in value:
                if cost[source][v] > cost[source][k] + weight[k][v]:
                    cost[source][v] = cost[source][k] + weight[k][v]
                    update = True
    if not update:
        for o in range(vertice):
            print((*([n if n != float("INF") else "INF" for n in cost[o]])))
        break
    vertice_cnt += 1

from collections import defaultdict

vertices, edges = (int(n) for n in input().split(" "))
connect = defaultdict(list)
cost_dp = [
    [float("inf") if n != m else 0 for n in range(vertices)] for m in range(vertices)
]
for e in range(edges):
    v1, v2, weight = (int(n) for n in input().split(" "))
    connect[v1].append([v2, weight])
    connect[v2].append([v1, weight])
    cost_dp[v1][v2] = weight
for neg in range(2):
    updated = 0
    for t in range(vertices):
        for i in range(vertices):
            for k in range(vertices):
                if cost_dp[i][k] > cost_dp[i][t] + cost_dp[t][k]:
                    updated = 1
                    cost_dp[i][k] = cost_dp[i][t] + cost_dp[t][k]
if neg == 1 and updated:
    print("NEGATIVE CYCLE")
else:
    for ve in range(vertices):
        ans = ["INF" if n == float("inf") else n for n in cost_dp[ve]]
        print((*ans))

-vertice, edge = list(map(int, input().split(" "))) -cost = [[0 if m == n else float("inf") for n in range(vertice)] for m in range(vertice)] -link = defaultdict(dict) -weight = defaultdict(dict) -for e in range(edge): -    i, j, w = list(map(int, input().split(" "))) -    link[i] = link.get(i, set()) | {j} -    weight[i].update({j: w}) -vertice_cnt = 0 -while 1: -    if vertice_cnt >= vertice: -        print("NEGATIVE CYCLE") -        break -    update = False -    for source in range(vertice): -        for k, value in list(link.items()): -            for v in value: -                if cost[source][v] > cost[source][k] + weight[k][v]: -                    cost[source][v] = cost[source][k] + weight[k][v] -                    update = True -    if not update: -        for o in range(vertice): -            print((*([n if n != float("INF") else "INF" for n in cost[o]]))) -        break -    vertice_cnt += 1 +vertices, edges = (int(n) for n in input().split(" ")) +connect = defaultdict(list) +cost_dp = [ +    [float("inf") if n != m else 0 for n in range(vertices)] for m in range(vertices) +] +for e in range(edges): +    v1, v2, weight = (int(n) for n in input().split(" ")) +    connect[v1].append([v2, weight]) +    connect[v2].append([v1, weight]) +    cost_dp[v1][v2] = weight +for neg in range(2): +    updated = 0 +    for t in range(vertices): +        for i in range(vertices): +            for k in range(vertices): +                if cost_dp[i][k] > cost_dp[i][t] + cost_dp[t][k]: +                    updated = 1 +                    cost_dp[i][k] = cost_dp[i][t] + cost_dp[t][k] +if neg == 1 and updated: +    print("NEGATIVE CYCLE") +else: +    for ve in range(vertices): +        ans = ["INF" if n == float("inf") else n for n in cost_dp[ve]] +        print((*ans))