#include <stdio.h>          // printf(), scanf()
#include <stdbool.h>

#define MAX_V 100
#define min(a, b) ((a) < (b) ? (a) : (b))

static long INF = (1L << 62);
long d[MAX_V][MAX_V];
int V;

void
warshall_floyd()
{
	int i, j, k;

	for (k = 0; k < V; ++k)
	{
		for (i = 0; i < V; ++i)
		{
			if (d[i][k] == INF)
				continue;

			for (j = 0; j < V; ++j)
			{
				if (d[k][j] != INF)
					d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
			}
		}
	}
}

int
main(int argc, char** argv)
{
	int E;
	int s, t, c;
	int i, j;

	scanf("%d %d", &V, &E);
	for (i = 0; i < V; ++i)
	{
		for (j = 0; j < V; ++j)
			d[i][j] = (i == j) ? 0 : INF;
	}

	for (i = 0; i < E; ++i)
	{
		scanf("%d %d %d", &s, &t, &c);
		d[s][t] = c;
	}

	warshall_floyd();
	bool negative = false;
	for (i = 0; i < V; ++i)
	{
		if (d[i][i] < 0)
			negative = true;
	}

	if (negative)
		printf("NEGATIVE CYCLE\n");

	else
	{
		for (i = 0; i < V; ++i)
		{
			for (j = 0; j < V; ++j)
			{
				if (j != 0)
					printf(" ");
					
				if (d[i][j] == INF)
					printf("INF");
				else
					printf("%ld", d[i][j]);
			}

			printf("\n");
		}
	}

	return 0;
}