#include<stdio.h>
int gm[249][249];
int main()
{
	int m,n;
	while(scanf("%d%d",&m,&n)!=EOF)
	{
		if(m==0)
			break;
	int i,j;
	for(i=0;i<m;i++)
		for(j=0;j<m;j++)
			gm[i][j]=(i==j?0:1000000009);
	int a,b,x;
	for(i=0;i<n;i++){
		scanf("%d%d%d",&a,&b,&x);
		if(a!=b&&gm[a][b]>x)
		{
		gm[a][b]=x;
		}
	}
	int k;
	  for(k=0;k<m;k++){
            for(i=0;i<m;i++){  
                for(j=0;j<m;j++)  
            {  
                if(gm[i][j]>gm[i][k]+gm[k][j])  
                    gm[i][j]=gm[i][k]+gm[k][j];  
				}}}
	  int t=0;
	for(i=0;i<m;i++)
			if(gm[i][i]<0)
				t++;
	if(t>0)
		printf("NEGATIVE CYCLE\n");
	else
	{
	for(i=0;i<m;i++){
		for(j=0;j<m;j++)
		{
		if(gm[i][j]>1000000000)
		{printf("INF ");
		/*if(j<3)
			printf(" ");*/
		}
		else
		{printf("%d ",gm[i][j]);
		/*if(j<3)
			printf(" ");*/
		}
		}printf("\n");
	}
	}
	}
	return 0;
}
