#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <climits>
#define ATCODER

class warshall_floyd
{
private:
    int node_num;
    bool is_negative_graph;
    std::vector<std::vector<long long>> cost_matrix;//隣接行列を構築
    std::vector<std::vector<int>> pred;//経路（遷移元）を保持
   
public:
    warshall_floyd(const int node_num, const std::vector<std::vector<long long>> &adj_matrix);
    bool get_is_negative_graph() const;
    bool get_is_negative_pass(int start, int end) const;
    long long get_cost(int start, int end) const;
    std::vector<int> get_min_path(int start, int end) const;
};

warshall_floyd::warshall_floyd(const int node_num, 
        const std::vector<std::vector<long long>> &adj_matrix):
    cost_matrix(adj_matrix),
    node_num(node_num),
    is_negative_graph(false),
    pred(node_num + 1, std::vector<int>(node_num + 1, INT_MAX))
{
    //predの初期化
    for (int i = 0; i <= node_num; i++) {
        for (int j = 0; j <= node_num; j++) {
            if (i == j) pred[i][j] = -1;
            else if (adj_matrix[i][j] < LLONG_MAX) {
                pred[i][j] = i;
            }
        }
    }
    //ワーシャルフロイドの更新式
    for (int k = 0; k <= node_num; k++) {
        for (int i = 0; i <= node_num; i++) {
            for (int j = 0; j <= node_num; j++) {
                if (cost_matrix[i][k] < LLONG_MAX && cost_matrix[k][j] < LLONG_MAX) {
                    if (cost_matrix[i][k] + cost_matrix[k][j] < cost_matrix[i][j]) {
                        cost_matrix[i][j] = cost_matrix[i][k] + cost_matrix[k][j];
                        //経路復元用
                        //pred[i][j]にはi→jの最短経路におけるjの1つ前の頂点が入る。
                        //pred[k][j]にはk→jの最短経路におけるjの1つ前の頂点が入っている。
                        //この処理を通るということは最短経路がkを使った経路に変わる
                        //ということでありi→jへの経路の中にk→jの最短経路を含むことになる。
                        //従って新しいi→jにおけるjの１つ前の頂点は
                        //k→jにおけるjの１つ前の頂点、すなわちpred[k][j]となる。
                        pred[i][j] = pred[k][j];
                    }
                }
            }
        }
    }

    //負のサイクル検出
    for (int i = 0; i <= node_num; i++) {
        //自分への距離が負になるならその頂点は負のサイクルに含まれる
        if (cost_matrix[i][i] < 0) {
            for (int j = 0; j <= node_num; j++) {
                //負のサイクルに含まれる頂点から辿れる頂点も負のサイクルになる
                if (i == j) continue;
                if (cost_matrix[i][j] < LLONG_MAX && cost_matrix[j][j] >= 0)
                    cost_matrix[j][j] = -1;
            }
            is_negative_graph = true;
            //break;
        }
    }
}

bool warshall_floyd::get_is_negative_graph() const {
    return is_negative_graph;
}

bool warshall_floyd::get_is_negative_pass(int start, int end) const {
    //startからendにたどり着けない場合はfalseを返す
    if (cost_matrix[start][end] < LLONG_MAX) {
        //startからend辿りつける場合、
        //endが負のサイクルに含まれるならtrueを返す
        if (cost_matrix[end][end] < 0) return true;
    }
    return false;
}


long long warshall_floyd::get_cost(int start, int end) const {
    return cost_matrix[start][end];
}

std::vector<int> warshall_floyd::get_min_path(int start, int end) const {
    int node = end;
    std::vector<int> vec;
    vec.push_back(node);
    //終点から始点までの経路をたどる
    while (1) {
        //負のサイクルを含む頂点or
        //始点から辿れない頂点or
        //始点であれば終了
        if (cost_matrix[node][node] < 0 || 
            pred[start][node] >= INT_MAX || 
            pred[start][node] == -1) break;
        node = pred[start][node];
        vec.push_back(node);
    }
    std::reverse(vec.begin(), vec.end());
    return vec;
}

int main()
{
#ifndef ATCODER
    int node_num, edge_num;
    std::cin >> node_num;
    std::cin >> edge_num;
    //std::cin >> r;
    std::vector<std::vector<long long>> 
        adj_matrix(node_num + 1, std::vector<long long>(node_num + 1, LLONG_MAX));
    for (int i = 0; i <= node_num; i++) adj_matrix[i][i] = 0;
    for (int i = 0; i < edge_num; i++) {
        int s, t;
        long long d;
        std::cin >> s;
        std::cin >> t;
        std::cin >> d;
        adj_matrix[s][t] = d;
    }
    warshall_floyd wf(node_num, adj_matrix);
    if (true || wf.get_is_negative_graph() == false) {
        for (int i = 1; i <= node_num; i++) {
            for (int j = 1; j <= node_num; j++) {
                long long cost = wf.get_cost(i, j);
                if (wf.get_is_negative_pass(i, j) == true) {
                    std::cout << "NEG";
                }
                else{
                    if (cost == LLONG_MAX)
                        std::cout << "INF";
                    else
                        std::cout << cost;
                    std::vector<int> path = wf.get_min_path(i, j);
                }
                if (j < node_num) std::cout << " ";
                
            }
            std::cout << "\n";
        }
    }
    else {
        std::cout << "NEGATIVE CYCLE\n";
    }
#else
    int N, M;
    std::cin >> N;
    std::cin >> M;
    std::vector<std::vector<long long>> 
        adj_matrix(N + 1, std::vector<long long>(N + 1, LLONG_MAX));
    for (int i = 0; i <= N; i++) adj_matrix[i][i] = 0;
    for (int i = 0; i < M; i++) {
        int a, b;
        long long c;
        std::cin >> a;
        std::cin >> b;
        std::cin >> c;
        adj_matrix[a][b] = -c;
    }
    warshall_floyd wf(N, adj_matrix);
    if (wf.get_is_negative_pass(1, N) == false)
        std::cout << -wf.get_cost(1, N) << "\n";
    else
        std::cout << "inf\n";
#endif

}



Measured memory_bytes: 20224