#include<stdio.h>
int d[1000][1000];
int M=2100000000;
int wafl(int v,int e,int *a,int *b,int *c){
  int i,j,k;
  for(i=0;i<v;i++){
    for(j=0;j<v;j++)d[i][j]=M;
    d[i][i]=0;
  }
  for(i=0;i<e;i++)d[a[i]][b[i]]=c[i];
  for(k=0;k<v;k++){
    for(i=0;i<v;i++){
      for(j=0;j<v;j++){
	if(d[i][k]==M||d[k][j]==M)continue;
	if(d[i][j]>d[i][k]+d[k][j])d[i][j]=d[i][k]+d[k][j];
      }
    }
  }
  for(i=0;i<v;i++){
    if(d[i][i])return 1;
  }
  return 0;
}
int main(){
  int n,m,i,j,a[100010],b[100010],c[100010];
  scanf("%d %d",&n,&m);
  for(i=0;i<m;i++)scanf("%d %d %d",&a[i],&b[i],&c[i]);
  if(wafl(n,m,a,b,c))printf("NEGATIVE CYCLE\n");
  else{
    for(i=0;i<n;i++){
      for(j=0;j<n;j++){
	if(j)printf(" ");
	d[i][j]-M?printf("%d",d[i][j]):printf("INF");
      }
      printf("\n");
    }
  }
  return 0;
}