#include<iostream>
#include<algorithm>
using namespace std;

const long long INF = 1e12;
const int MAX_V = 1000;
const int MAX_E = 2000;

long long d[MAX_V][MAX_V];
int V, E;

void warshall_floyd() {
	for (int k = 0; k < V; k++)
		for (int i = 0; i < V; i++)
			for (int j = 0; j < V; j++)
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
int main() {
	cin >> V >> E;
	for (int i = 0; i < MAX_V; i++) {
		for (int j = 0; j < MAX_V; j++) {
			if(i != j) d[i][j] = INF;
			else d[i][j] = 0;
		}
	}
	for (int i = 0; i < E; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		d[a][b] = c;
	}
	warshall_floyd();
	for (int i = 0; i < V; i++) {
		if (d[i][i] != 0) {
			cout << "NEGATIVE CYCLE" << endl;
			return 0;
		}
	}
	for (int i = 0; i < V; i++) {
		for (int j = 0; j < V; j++) {
			if (j) cout << " ";
			if (d[i][j] > 1e10) cout << "INF";
			else cout << d[i][j];
		}
		cout << endl;
	}
}
