#include <stdio.h>
#define INF 1999999999//1 #define INF 999999999 
int v,e;
long long a[110][110];//1 int 改成 long long  
void floyd(){
    int i,j,k;
    for(k=0;k<v;k++)
        for(i=0;i<v;i++)
            for(j=0;j<v;j++)
                if(a[i][j]>a[i][k]+a[k][j])
                    a[i][j]=a[i][k]+a[k][j];
}
int main(){
    int i,j,s,t,d;
    scanf("%d%d",&v,&e);
    for(i=0;i<v;i++)
        for(j=0;j<v;j++)
            a[i][j]=(i==j)?0:INF;
    for(i=1;i<=e;i++){
        scanf("%d%d%d",&s,&t,&d);
        a[s][t]=d;
    }
    floyd();
    for(i=0;i<v;i++)//判断?? 
        if(a[i][i]<0){
            printf("NEGATIVE GYCLE\n");
            return 0;
        }
    for(i=0;i<v;i++){
        for(j=0;j<v;j++){
            if(j)printf(" ");
            if(a[i][j]==INF)printf("INF");
            else printf("%lld",a[i][j]);//1 原来printf("%d",a[i][j]);
        }
        printf("\n");
    }
    return 0;
}