#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int v,e;
  cin>>v>>e;
  int g[v][v];
  int INF=1LL<<55LL;
  for(int i=0;i<v;i++)
    for(int j=0;j<v;j++)
      g[i][j]=(i!=j)*INF;
  for(int i=0;i<e;i++){
    int s,t,d;
    cin>>s>>t>>d;
    g[s][t]=d;
  }
  for(int k=0;k<v;k++)
    for(int i=0;i<v;i++)
      for(int j=0;j<v;j++)
	g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
  for(int i=0;i<v;i++){
    if(g[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(g[i][j]>=INF/2) cout<<"INF";
      else cout<<g[i][j];
    }
    cout<<endl;
  }
  return 0;
}
#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;
}