//#include<cstdio>
//#include<algorithm>
//#include<iostream>
//#include<cstring>
//using namespace std;
#include<stdio.h>
#include<string.h>
#define MAX 0x3f3f3f3f
int a[105][105];
int min(int x,int y){
    if(x<=y)
        return x;
    else
        return y;
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    memset(a,MAX,sizeof(a));
    for(int i=0,x,y;i<m;i++){
        scanf("%d%d",&x,&y);
        scanf("%d",&a[x][y]);
    }
    for(int k=0;k<n;k++)
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++){
                a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
                if(a[i][j]!=min(a[i][j],a[i][k]+a[k][j])){
                    printf("NEGATIVE CYCLE\n");
                    return 0;
                }
            }
//    for(int k=0;k<n;k++)
//        for(int i=0;i<n;i++)
//            for(int j=0;j<n;j++){
//                if(a[i][j]!=min(a[i][j],a[i][k]+a[k][j])){
//                    printf("NEGATIVE CYCLE\n");
//                    return 0;
//                }
//            }
    for(int i=0;i<n;i++)
        a[i][i]=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(a[i][j]==1061109567)
                printf("INF");
            else
                printf("%d",a[i][j]);
            if(j!=n-1)
                printf(" ");
        }
        printf("\n");
    }
    return 0;
}

