def warshall_floyd(graph, edges):

    N = len(graph)

    inf = Infinity()  # !_!

    for i in range(N):

        for j in range(N):

            if i == j:

                graph[i][j] = 0

            else:

                graph[i][j] = inf

    for e in edges:

        graph[e.source][e.destination] = e.weight

    for k in range(N):

        for i in range(N):

            for j in range(N):

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

    for k in range(N):

        for i in range(N):

            for j in range(N):

                if inf in (graph[i][j], graph[i][k], graph[k][j]):  # !_!

                    continue

                if graph[i][j] > graph[i][k] + graph[k][j]:

                    raise NegativeCycleError



def main():

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

    graph = [[None] * V for _ in range(V)]

    edges = []

    for _ in range(E):

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

        edges.append(Edge(s, t, d))

    try:

        warshall_floyd(graph, edges)

        for g in graph:

            print(" ".join(map(str, g)))

    except NegativeCycleError:

        print("NEGATIVE CYCLE")



class Infinity(object):

    def __eq__(self, other):

        return other is self



    def __lt__(self, other):

        return False



    def __gt__(self, other):

        return True



    def __add__(self, other):

        return self



    def __radd__(self, other):

        return self



    def __str__(self):

        return "INF"

    __repr__ = __str__



class NegativeCycleError(Exception):

    pass



class Edge(object):

    def __init__(self, source, destination, weight):

        self.source = source

        self.destination = destination

        self.weight = weight



if __name__ == "__main__":

    main()
def warshall_floyd(graph, edges):

    N = len(graph)

    for i in range(N):

        for j in range(N):

            if i == j:

                graph[i][j] = 0

            else:

                graph[i][j] = Infinity()

    for e in edges:

        graph[e.source][e.destination] = e.weight

    for k in range(N):

        for i in range(N):

            for j in range(N):

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

    for i in range(N):

        if graph[i][i] < 0:

            raise NegativeCycleError



def main():

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

    graph = [[None] * V for _ in range(V)]

    edges = []

    for _ in range(E):

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

        edges.append(Edge(s, t, d))

    try:

        warshall_floyd(graph, edges)

        for g in graph:

            print(" ".join(map(str, g)))

    except NegativeCycleError:

        print("NEGATIVE CYCLE")



class Infinity(object):

    def __eq__(self, other):

        return other is self



    def __lt__(self, other):

        return False



    def __gt__(self, other):

        return True



    def __add__(self, other):

        return self



    def __radd__(self, other):

        return self



    def __str__(self):

        return "INF"

    __repr__ = __str__



class NegativeCycleError(Exception):

    pass



class Edge(object):

    def __init__(self, source, destination, weight):

        self.source = source

        self.destination = destination

        self.weight = weight



if __name__ == "__main__":

    main()
def warshall_floyd(graph, edges):
    N = len(graph)
    inf = Infinity()  # !_!
    for i in range(N):
        for j in range(N):
            if i == j:
                graph[i][j] = 0
            else:
                graph[i][j] = inf
    for e in edges:
        graph[e.source][e.destination] = e.weight
    for k in range(N):
        for i in range(N):
            for j in range(N):
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if inf in (graph[i][j], graph[i][k], graph[k][j]):  # !_!
                    continue
                if graph[i][j] > graph[i][k] + graph[k][j]:
                    raise NegativeCycleError


def main():
    V, E = list(map(int, input().split()))
    graph = [[None] * V for _ in range(V)]
    edges = []
    for _ in range(E):
        s, t, d = list(map(int, input().split()))
        edges.append(Edge(s, t, d))
    try:
        warshall_floyd(graph, edges)
        for g in graph:
            print(" ".join(map(str, g)))
    except NegativeCycleError:
        print("NEGATIVE CYCLE")


class Infinity(object):
    def __eq__(self, other):
        return other is self

    def __lt__(self, other):
        return False

    def __gt__(self, other):
        return True

    def __add__(self, other):
        return self

    def __radd__(self, other):
        return self

    def __str__(self):
        return "INF"

    __repr__ = __str__


class NegativeCycleError(Exception):
    pass


class Edge(object):
    def __init__(self, source, destination, weight):
        self.source = source
        self.destination = destination
        self.weight = weight


if __name__ == "__main__":
    main()

def warshall_floyd(graph, edges):
    N = len(graph)
    for i in range(N):
        for j in range(N):
            if i == j:
                graph[i][j] = 0
            else:
                graph[i][j] = Infinity()
    for e in edges:
        graph[e.source][e.destination] = e.weight
    for k in range(N):
        for i in range(N):
            for j in range(N):
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
    for i in range(N):
        if graph[i][i] < 0:
            raise NegativeCycleError


def main():
    V, E = list(map(int, input().split()))
    graph = [[None] * V for _ in range(V)]
    edges = []
    for _ in range(E):
        s, t, d = list(map(int, input().split()))
        edges.append(Edge(s, t, d))
    try:
        warshall_floyd(graph, edges)
        for g in graph:
            print(" ".join(map(str, g)))
    except NegativeCycleError:
        print("NEGATIVE CYCLE")


class Infinity(object):
    def __eq__(self, other):
        return other is self

    def __lt__(self, other):
        return False

    def __gt__(self, other):
        return True

    def __add__(self, other):
        return self

    def __radd__(self, other):
        return self

    def __str__(self):
        return "INF"

    __repr__ = __str__


class NegativeCycleError(Exception):
    pass


class Edge(object):
    def __init__(self, source, destination, weight):
        self.source = source
        self.destination = destination
        self.weight = weight


if __name__ == "__main__":
    main()

-    inf = Infinity()  # !_! -                graph[i][j] = inf +                graph[i][j] = Infinity() -    for k in range(N): -        for i in range(N): -            for j in range(N): -                if inf in (graph[i][j], graph[i][k], graph[k][j]):  # !_! -                    continue -                if graph[i][j] > graph[i][k] + graph[k][j]: -                    raise NegativeCycleError +    for i in range(N): +        if graph[i][i] < 0: +            raise NegativeCycleError