#include<stdio.h>
#define INT_MAX 0x7f7f7f7f
struct EDGE
{
    int x, y, z;
}a[9905];
int v, e, dis[105][105];
int floyd()
{
    for(int i = 0; i < v; i++)
        for(int j = 0; j < v; j++)
            dis[i][j] = INT_MAX;
    for(int i = 1; i <= e; i++)
        dis[a[i].x][a[i].y] = a[i].z;

    for(int k =0; k < v; k++)
        for(int i = 0; i < v; i++){
            dis[i][i] = 0;
            for(int j = 0; j < v; j++)
                if(dis[i][k] != INT_MAX && dis[k][j] != INT_MAX)
                    if(dis[i][j] > dis[i][k] + dis[k][j])
                        dis[i][j] = dis[i][k] + dis[k][j];
            if(dis[i][i] < 0) return 0;
        }
    return 1;
}
int main()
{
    scanf("%d%d", &v, &e);
    for(int i = 1; i <= e; i++)
        scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].z);
    if(floyd())
        for(int i = 0; i < v; i++)
            for(int j = 0; j < v; j++)
                if(dis[i][j] != INT_MAX) printf("%d", dis[i][j]), putchar(" \n"[j == v - 1]);
                else printf("INF"), putchar(" \n"[j == v - 1]);
    else printf("NEGATIVE CYCLE\n");
    return 0;
}
