#include<stdio.h>
#define INF 0x3f3f3f3f
#define ll long long
#define MAXN 100+10
ll map[MAXN][MAXN];
ll min(ll x,ll y)
{
	if(x>y)return y;
	else return x;
}
void init(int N)
{
	int i,j;
	for(i=0;i<=N;i++)
	{
		for(j=0;j<=N;j++)
		{
			map[i][j]=INF;
		}
		map[i][i]=0;
	}
}
void floyd(int N)
{
	ll i,k,j;
	for(k=0;k<N;k++)
	{
		for(i=0;i<N;i++)
		{
			for(j=0;j<N;j++)
			{
//				if(map[i][j]<INF&&map[k][j]<INF)
				map[i][j]=min(map[i][j],map[i][k]+map[k][j]);
			}
		}
	}
}
int main()
{
	ll N,E;
	scanf("%lld%lld",&N,&E);
	init(N);
	ll i,j;
	for(i=0;i<E;i++)
	{
		ll s,t,d;
		scanf("%lld%lld%lld",&s,&t,&d);
		if(map[s][t]>d)map[s][t]=d;
	}
	floyd(N);
	int flag=0;
	for(i=0;i<N;i++)
	{
		if(map[i][i]<0)
		{
			flag=1;
			printf("NEGATIVE CYCLE\n");
			break;
		}
	}
	if(flag==0)
	for(i=0;i<N;i++)
	{
		for(j=0;j<N;j++)
		{
			if(j)printf(" ");
			if(map[i][j]==INF)printf("INF");
			else printf("%lld",map[i][j]);
		}
		printf("\n");
	}
	return 0;
}
