/**
 * @brief  ??¨?????????????????????????????????Floyd-Warshall??¢?????´??????????????±???
 * @note   ??¢??£URL: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_C
 * @date   2016/02/21 ~ 2017/01/03
 */



//****************************************
// ???????????????????????????????????????????????????
//****************************************


#include <iostream>
#include <utility>
#include <algorithm>
#include <vector>



//****************************************
// ???????????§????????¢?????????????????????
//****************************************

#define GRAPH_BEGIN namespace graph {
#define GRAPH_END   }



//****************************************
// ????????????????§????
//****************************************

GRAPH_BEGIN



//****************************************
// ?§????????????????
//****************************************

using weight_t   = std::int32_t;  /**< ???(u, v)????????????w?????¨?????? */
using index_t    = std::int32_t;  /**< ??????v??????????????¨??????       */
using capacity_t = weight_t;      /**< ???(u, v)??????????????¨??????    */



namespace limits {
    enum {  // scoped??§????????????????????????????????????enum(strongly-typed enum)??§?????????
        inf = std::numeric_limits<weight_t>::max(),  /**< @brief ???????????¨???????????´???????????¨????????????     */
        nil = std::numeric_limits<index_t>::min(),   /**< @brief ?????????????????¨???????????´???????????¨???????????? */
    };
}



/**
 * @brief  ????????????????§???????(scoped enum)
 * @detail (u, v) ??? E??§??????u??????????????°??????v?????°????????§??????
 *         ?????????????????????????????£??\????????¨?????????????????????????????§??????
 *         ??°???????????????????????£??\???????????¨???????????????????????????????????¢??????????????¨???????????????????¢?????????????
 */
enum struct vcolor : std::int32_t {
    white,  /**< ??????????????? */
    black,  /**< ??¢???????????? */
    gray,   /**< ??¢???????????? */
};

/**
 * @brief ??°????????¨?????????(??????) 
 */
struct vertex {
    union {
        weight_t d;       /**< ?§????s??????????????¢  */
        weight_t key;     /**< Prim?????¢?????´???????????????????????¨????±?????????????????????¨????????¶?????? */
    };
    index_t pi;           /**< ????????????(?????????) */
    union {
        vcolor color;     /**< ????????????        */
        bool  visited;    /**< ????????????????     */
    };
    // weight_t f;           /**< ??????????????°(DFS?????????????????????????????????????????¨??????????????????)     */
    vertex() : d(0), pi(0), color(vcolor::white)/*, f(0)*/ {}
};

/**
 * @brief ??°????????¨??¨??????(???)
 * @note  G = (V, E)???????????¢??°w???????????????????????°????????¨????????¨???
 *        ???(u, v) ??? E????????????w(u, v)??¨??¨?????????
 */
struct edge {
    index_t  src;   /**< ???????§????u */
    index_t  dst;   /**< ????????????v */
    union {
        weight_t w;     /**< ???(u, v)????????????(?????????) */
        capacity_t c;   /**< ???(u, v)????????? */
    };
    edge() = default;
    edge(index_t src, index_t dst) : src(src), dst(dst), w(1) {}
    edge(index_t src, index_t dst, weight_t w) : src(src), dst(dst), w(w) {}
};



using edges_t    = std::vector<edge>;      /**< ??°??????G=(V, E)????????????E   */
using vertices_t = std::vector<vertex>;    /**< ??°??????G=(V, E)???????????????V */
using array_t    = std::vector<weight_t>;  /**< ??????w?????????  */
using indices_t  = std::vector<index_t>;   /**< ????????????????????? */
using matrix_t   = std::vector<array_t>;   /**< ??°??????G?????£??\????????¨???(???????????¨????????¨???) */
using graph_t    = std::vector<edges_t>;   /**< ??°??????G?????£??\???????????¨???(???????????????????????¨??????) */



//****************************************
// ??¢??°?????????
//****************************************

/**
 * @brief  ???????¨??????¢?????´???????????§??????Floyd-Warshall??¢?????´?????????
 *
 * @note   Floyd-Warshall??¢?????´???????????§???????????????????????????????????????. ????????§???????´????p = <v0,v1,...,vl>???v0??¨vl??\???????????????
 *         ?????????????????????{ v1,v2,...,v(l-1) }???????????????????????????(intermediate)????????§??????
 *
 *         Floyd-Warshall??¢?????´??????????????\????????????????????\????????????. G??????????????????V = { 0,1,...,n-1 }??§????????¨????????????????????§???
 *         ??????k???????????????????????¨?????????{ 0,1,...k }????????????. ??????????????????i,j ??? V???????????????i??????j???????????§????????????????????????????????????
 *         ?????? { 0,1,...,k }????±?????????????????????????????????????????????§????°?????????????????????????p??¨??????. (???p???????´???§??????)
 *
 *         Floyd-Warshall??¢?????´??????????????????p??¨?????????????????????????????????{ 0,1,...,k-1 }????±???????(??¨???????????¶????????§???)i??????j?????????????????¨?????¢???????§£?????????
 *         ????????¢??????k??????p?????????????????§?????????????????????????????????
 *
 *         * k??????p?????????????????§???????????°???p?????????????????????????????????{ 0,1,...,k-1 }????±?????????????. ???????????£????????????????????????????????????{ 0,1,..,k-1 }????±???????
 *           ??????i??????j???????????????????????????????????????????????????{ 0,1,...,k }????±???????i??????j?????????????????§??????
 *
 *         * k??????p???????????????????????°???p???i~(p1)~>k~(p2)~>j??¨????§£??????. p1?????????????????????????????????{ 0,1,...,k }????±???????i??????j?????????????????§??????
 *           ??????????????????????°???????????¨???????????????????. ??????k??????p1????????????????????§??????????????????p1?????????????????????????????????{ 0,1,...,k-1 }????±???????.
 *           ???????????£?????? p1?????????????????????????????????{ 0,1,...,k-1 }????±???????i??????k?????????????????§??????
 *           ????§???????p2?????????????????????????????????{ 0,1,...,k-1 }????±?????????????k????????????j?????????????????§??????
 *
 *         ????????????????????\???????????????????????¨??????????????°?????????????????????. ??????????????????????????????{ 0,...,k }????±?????????????i??????j???????????????????????????dij^(k+1)??¨??????
 *         k = -1?????¨??????-1????????§??????????????????????????????????????????????????????i????????????j???????????????????????????1??????????????????. ???????????????????????????1??¬?????????????????????????????????
 *         dij^(0) = wij??§??????. ?????£??????dij^(k+1)????????°????????????
 *           dij^(k+1) = { wij                            k = -1?????¨???
 *                       min(dij^(k), dik^(k) + djk^(k))  k >= 0?????¨??? }
 *         ?????????. ????????????????????????????????????????????????????????????{ 0,..,n-1 }????±??????????????????????D^(n-1) = (dij^(n-1))????????????????§£????????????
 *         ???????????????????????????i,j ??? V???????????????dij^(d) = ?´(i, j)???????????????. ???????????????????????´????????????0,1,...,k-1?????????????????´????????°????????????
 *
 *         i,j,k = 0,1,...,n-1????????????dij^(k)????¨????????????????Floyd-Warshall??¢?????´???????????§?????(n^3)????????????????????§????????????
 *         ??????????±\??´?????????????????¨???????????§????????????????????????????????¨???????????????????¶?????????£???????????(n^2)???????????§????????§??????
 *
 * @note   3??????for??????????????????????????(1)????????§????????§???????????????????????¢?????´?????????????????????????????(n^3)??§??????
 *         ?????????????????????????????§?????£?????????????????????????§?????????????????????-?¨????????????????????????°????°???????
 *         ???????????£??????Floyd-Warshall??¢?????´????????????????§???§????????\?????°???????????????????????????????????¨?????§??????
 *
 */
matrix_t floyd_warshall(const matrix_t& W)
{
    index_t n = W.size();  // n = W.rows
    matrix_t D(n, array_t(n, limits::inf));
    for (index_t i = 0; i < n; ++i) { std::copy(W[i].begin(), W[i].end(), D[i].begin()); D[i][i] = 0; }

    
    for (index_t k = 0; k < n; ++k) {
        for (index_t i = 0; i < n; ++i) {
            for (index_t j = 0; j < n; ++j) {
                // ??????????????°a != ??????????????????a + ??? = ??? + a = ???(?????????a + (-???) = (-???) + a = (-???))?????????????????????
                if (D[i][k] != limits::inf && D[k][j] != limits::inf) {
                    D[i][j] = std::min(D[i][j], D[i][k] + D[k][j]);
                }
            }
        }
    }
    return D;
}




//****************************************
// ?????????????????????
//****************************************

GRAPH_END



//****************************************
// ??¨?????????????????????
//****************************************

int main(void)
{
    using namespace std;
    using namespace graph;
    
    int n, e, u, v, c;
    cin >> n >> e;
    matrix_t W(n, array_t(n, limits::inf));
    for (int i = 0; i < n; i++) { W[i][i] = 0; }

    for (int i = 0; i < e; i++) {
        cin >> u >> v >> c;
        W[u][v] = c;
    }

    matrix_t D = floyd_warshall(W);

    bool neg = false;
    for (int i = 0; i < n; i++) { if (D[i][i] < 0) { neg = true; } }

    if (neg) {
        cout << "NEGATIVE CYCLE" << endl;
    }
    else {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (j) cout << " ";
                if (D[i][j] == limits::inf) cout << "INF";
                else                        cout << D[i][j];
            }
            cout << endl;
        }
    }
    
    return 0;
}

Measured memory_bytes: 3220