#include <stdio.h>
#include <stdlib.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define INF ((1LL<<62)-(1LL<<31))
#define min(p,q)((p)<(q)?(p):(q))

//ワーシャルフロイド
//頂点数（と隣接行列）を引いて全点間最短距離を返す
//O(V^3)
//*
ll cost[110][110];
ll dddd[110][110];
void waasharuhuroido(ll n){
	rep(i,0,n)rep(j,0,n)dddd[i][j]=cost[i][j];//辺が無いところはINFにする前処理が必要
	rep(k,0,n)rep(i,0,n)rep(j,0,n)dddd[i][j]=min(dddd[i][j],dddd[i][k]+dddd[k][j]);
	rep(k,0,n)rep(i,0,n)rep(j,0,n){
		if(dddd[i][j]>dddd[i][k]+dddd[k][j]){
			puts("NEGATIVE CYCLE");
			exit(0);
		}
	}
}
//*/

int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	rep(i,0,n)rep(j,0,n)if(i!=j)cost[i][j]=INF;
	rep(_,0,m){
		int x,y;
		ll c;
		scanf("%d%d%lld",&x,&y,&c);
		cost[x][y]=c;
	}
	waasharuhuroido(n);
	rep(i,0,n){
		rep(j,0,n){
			if(dddd[i][j]>2e9)printf("INF%c",j==n-1?10:32);
			else printf("%lld%c",dddd[i][j],j==n-1?10:32);
		}
	}
}
