#include <iostream>
#include <algorithm>
using namespace std;

const long long INF = 10000000000LL;
long long G[100][100];

int main() {
  int V, E; cin >> V >> E;
  for(int i = 0; i < V; i++) {
    for(int j = 0; j < V; j++) {
      G[i][j] = INF;
    }
    G[i][i] = 0;
  }
  for(int i = 0; i < E; i++) {
    long long from, to, d;
    cin >> from >> to >> d;
    G[from][to] = min(G[from][to], d);
  }
  for(int k = 0; k < V; k++)
    for(int i = 0; i < V; i++)
      for(int 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]);

  bool negative_loop = false;
  for(int v = 0; v < V; v++)
    if(G[v][v] < 0) negative_loop = true;

  if(negative_loop) {
    cout << "NEGATIVE CYCLE" << endl;
  }
  else {
    for(int i = 0; i < V; i++) {
      for(int j = 0; j < V; j++) {
        if(j != 0) cout << ' ';

        if(G[i][j] == INF) cout << "INF";
        else cout << G[i][j];
      }
      cout << endl;
    }
  }
}