#include <stdio.h>
#include <limits.h>
int main(){
	int n,m,s,i,j;
	scanf("%d%d",&n,&m);
	int e[m+1][3],dist[m+1],update=1,k,d[200][200];
	//printf("xxx");
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			if(i==j)d[i][j]=0;
			else d[i][j]=INT_MAX;
		}
	}
	for(i=0;i<m;i++){
		for(j=0;j<3;j++){
			scanf("%d",&e[i][j]);
		}
		d[e[i][0]][e[i][1]]=e[i][2];
	}
	for(i=0;i<n;i++){
		dist[i]=INT_MAX;
	}
	dist[s]=0;
	for(i=0;i<n-1;i++){
		update=0;
		for(j=0;j<m;j++){
			if(dist[e[j][0]]!=INT_MAX&&dist[e[j][1]]>dist[e[j][0]]+e[j][2]){
				dist[e[j][1]]=dist[e[j][0]]+e[j][2];
				update=1;
			}
		}
		if(update==0)break;
	}
	for(j=0;j<m;j++){
		if(dist[e[j][0]]!=INT_MAX&&dist[e[j][1]]>dist[e[j][0]]+e[j][2]){
			printf("NEGATIVE CYCLE\n");
			return 0;
		}
	}
	for(k=0;k<n;k++){
		for(i=0;i<n;i++){
			for(j=0;j<n;j++){
				if((d[i][k]!=INT_MAX&&d[k][j]!=INT_MAX)&&d[i][j]>d[i][k]+d[k][j]){
					d[i][j]=d[i][k]+d[k][j];
				}
			}
		}
	}
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			if(j>0)printf(" ");
			if(d[i][j]==INT_MAX){
				printf("INF");
			}
			else{
				printf("%d",d[i][j]);
			}
		}
		printf("\n");
	}
	return 0;
}
# define _CRT_SECUREj_NO_WARNINGS 1
# define _USE_MATH_DEFINES
# include <iostream>
# include <numeric>
# include <string>
# include <bitset>
# include <vector>
# include <algorithm>
# include <cstdlib>
# include <cstdio>
# include <cstring>
# include <cstdlib>
# include <iomanip>
# include <queue>
# include <sstream>
# include <climits>
# include <cmath>
# include <list>
# include <functional>
# include <string>
# include <ctime>
# include <set>
# include <forward_list>
# include <map>
# include <stack>
using namespace std;
# define INF ((int)(1<<25))
# define REP(i,n) for(int i=0;i<(int)n;i++)
# define FOR(i,n) REP(i,n)
# define FORI(i,k,n) for(int i=k;i<(int)n;i++)
# define TORAD 2.0*M_PI/360.0
# define INT(x) int x;cin>>x;
# define ALL(x) (x).begin(),(x).end()
# define RALL(x) (x).rbegin(),(x).rend()
# define DEBUG(x) cout<<#x<<":"<<x<<endl;
# define EPS 1e-12
#ifdef _MSC_VER
#include <intrin.h>
#define __builtin_popcount __popcnt
#endif
#define int long long
typedef long long lint;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
const int dx[4] = { 0,1,0,-1 }, dy[4] = { -1,0,1,0 };
template<class T> void debug(T a) { for (auto i : a)cout << i << endl; }

const int M = 110;
int f[M][M];
int v, e, r;

signed main()
{
	cin >> v >> e;
	FOR(i, M)FOR(j, M)f[i][j] = INT_MAX;
	FOR(i, M)f[i][i] = 0;
	FOR(i, e)
	{
		int s, t, d;
		cin >> s >> t >> d;
		f[s][t] = d;
	}

	FOR(k, M)
	{
		FOR(i, M)
		{
			FOR(j, M)
			{
				if (f[i][k] == INT_MAX || f[k][j] == INT_MAX)continue;
				f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
			}
		}
	}
	FOR(i, M)if (f[i][i] < 0) { cout << "NEGATIVE CYCLE" << endl; return 0; }

	FOR(i, v)
	{
		FOR(j, v)
		{
			if (j)cout << " ";
			if (f[i][j] == INT_MAX)cout << "INF";
			else cout << f[i][j];
		}
		cout << endl;
	}
}