#include <algorithm>
    #include <vector>
    #include <functional>
    #include <climits>
    #include <iostream> 
    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;
    }
     
    #define ATCODER
    #define ATCODER2
    int main()
    {
    #ifndef ATCODER
        int node_num, edge_num;
        std::cin >> node_num;
        std::cin >> edge_num;
        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 (wf.get_is_negative_graph() == false) {
            for (int i = 0; i < node_num; i++) {
                for (int j = 0; 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 - 1) std::cout << " ";
                    
                }
                std::cout << "\n";
            }
        }
        else {
            std::cout << "NEGATIVE CYCLE\n";
        }
    #else
    #ifdef ATCODER2
        int N, M;
        std::cin >> N;
        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++) {
            for (int j = 0; j < N; j++) {
                long long A;
                std::cin >> A;
                adj_matrix[i][j] = A;
            }
        }
        std::vector<std::vector<bool>>
            is_used(N + 1, std::vector<bool>(N + 1, false));
        warshall_floyd wf(N, adj_matrix);
     
        long long min_dist = 0;
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                if (wf.get_cost(i, j)!= adj_matrix[i][j]) {
                    std::cout << "-1\n";
                    return 0;
                }
                bool is_direct_path = true;
                for (int k = 0; k < N; k++) {
                    if (k != i && k != j) {
                        if (wf.get_cost(i, j) == wf.get_cost(i, k) + wf.get_cost(k, j)) {
                            is_direct_path = false;
                            break;
                        }
                    }
                }
                if (is_direct_path == true) {
                    min_dist += wf.get_cost(i, j);
                }
            }
        }
     
        std::cout << min_dist << "\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
    #endif
     
    }

Measured memory_bytes: 2048