# 目次

• 目次
  • 解説
  • 解答

# 解説

負の重みあり有効グラフのすべての頂点間の距離を求める問題.
負の重みがなければSingle source shortest pathsで使用したダイクストラで解ける.
負の重みがあればベルマンフォードで解けるが、$O(V^2E)$なので$O(V^3)$のフロイドワーシャルのほうが速い.

# 解答

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;

#define MAX_N 101
#define MAX_E 9901
#define W_INF (1L << 32)

Int dist[MAX_N][MAX_N];
bool negative = false;

void apsp(Int n) {
  loop(k,0,n) {
    loop(u,0,n) {
      if (dist[u][k] == W_INF) continue;
      loop(v,0,n) {
        if (dist[k][v] == W_INF) continue;
        dist[u][v] = min(dist[u][v], dist[u][k] + dist[k][v]);
      }
      
      if (dist[u][u] < 0) {
        negative = true;
        return;
      }
    }
  }
}


int main(void) {
  Int n, e, v, u, w;
  cin >> n >> e;
  loop(i,0,n) {
    loop(j,0,n) {
      dist[i][j] = (i == j) ? 0 : W_INF;
    }
  }
  
  loop(i,0,e) {
    cin >> u >> v >> w;
    dist[u][v] = w;
  }
  
  apsp(n);
  if (negative) cout << "NEGATIVE CYCLE" << endl;
  else {
    loop(u,0,n) {
      loop(v,0,n) {
        if (dist[u][v] == W_INF) cout << "INF";
        else cout << dist[u][v];
        if (v != n-1) cout << ' ';
      }
      cout << endl;
    }
  }
}