#include <stdio.h>
#define INF 1e12
#define min(a, b) ((a < b) ? a : b)

typedef long long int LL;
 
int main()
{
    int i, j, k;
    int v, e;
    int s, t, d;
    LL G[101][101];
 
    scanf("%d %d", &v, &e);
 
    for (i = 0; i < v; i ++) {
        for (j = 0; j < v; j++) {
            G[i][j] = (i == j) ? 0 : INF;
        }
    }
 
    for (i = 0; i < e; i++) {
        scanf("%d %d %d", &s, &t, &d);
        G[s][t] = d;
    }
 
    for (k = 0; k < v; k++) {
        for (i = 0; i < v; i++) {
            for (j = 0; j < v; j++) {
                if (G[i][k] != INF && G[k][j] != INF) {
                    G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
                }
            }
        }
    }
 
    for (i = 0; i < v; i++) {
        if (G[i][i] < 0) {
            printf("NEGATIVE CYCLE\n");
            return 0;
        }
    }
 
    for (i = 0; i < v; i++) {
        for (j = 0; j < v; j++) {
            printf(G[i][j] == INF ? "INF" : "%lld", G[i][j]);
            printf((j == v-1) ? "\n" : " ");
        }
    }
 
    return 0;
}