#include <bits/stdc++.h>

template <typename T>
struct Edge {
    Edge(const std::size_t from_, const std::size_t to_, const T cost_) : from{from_}, to{to_}, cost{cost_} {}
    Edge<T>& operator=(const Edge<T>&) = default;
    std::size_t from;
    std::size_t to;
    T cost;
    bool operator<(const Edge<T>& e) const  //inverse
    {
        return cost != e.cost ? cost > e.cost : to < e.to;
    }
};

template <typename T>
class Graph
{
public:
    Graph(const std::size_t v) : m_v{v}
    {
        m_table.resize(v);
        m_reversed_table.resize(v);
    }
    void addEdge(const std::size_t from, const std::size_t to, const T cost)
    {
        m_e++;
        m_table[from].push_back(Edge<T>{from, to, cost});
        m_reversed_table[to].push_back(Edge<T>{to, from, cost});
    }

    void TopologocalSort(std::vector<std::size_t>& srt) const
    {
        assert(srt.size() == m_v);
        std::vector<bool> yet(m_v, true);
        std::size_t pos = m_v - 1;
        for (std::size_t i = 0; i < m_v; i++) {
            dfs_topo(i, yet, srt, pos);
        }
    }

    void SCC(std::vector<std::size_t>& cmp) const
    {
        assert(cmp.size() == m_v);

        for (std::size_t i = 0; i < m_v; i++) {
            cmp[i] = 1;
        }

        std::size_t pos = m_v - 1;
        std::vector<std::size_t> st(m_v);
        for (std::size_t i = 0; i < m_v; i++) {
            if (cmp[i]) {
                dfs1_scc(i, cmp, st, pos);
            }
        }

        for (std::size_t i = 0; i < m_v; i++) {
            cmp[i] = INF;
        }

        std::size_t comp = 0;
        for (std::size_t i = 0; i < m_v; i++) {
            const std::size_t s = st[m_v - i - 1];
            if (cmp[s] == INF) {
                dfs2_scc(s, comp, cmp);
                comp++;
            }
        }
    }

    bool BellmanFord(const std::size_t s, std::vector<T>& d)
    {
        assert(s < m_v);
        assert(d.size() == m_v);
        for (std::size_t i = 0; i < m_v; i++) {
            d[i] = INF;
        }
        d[s] = 0;
        bool no_negative_loop = true;
        for (std::size_t i = 0; i < m_v; i++) {
            for (std::size_t v = 0; v < m_v; v++) {
                if (d[v] != INF) {
                    for (const auto& e : m_table[v]) {
                        if (d[e.to] > d[e.from] + e.cost) {
                            d[e.to] = d[v] + e.cost;
                            if (i == m_v - 1) {
                                d[e.to] = -INF;  // Confirm " -INF < min(possible_cost) * V "
                                no_negative_loop = false;
                            }
                        }
                    }
                }
            }
        }
        return no_negative_loop;
    }

    void Dijkstra(const std::size_t s, std::vector<T>& d)
    {
        assert(s < m_v);
        assert(d.size() == m_v);
        using P = std::pair<T, std::size_t>;
        std::priority_queue<P, std::vector<P>, std::greater<P>> q;
        for (std::size_t i = 0; i < m_v; i++) {
            d[i] = INF;
        }
        d[s] = 0;
        q.push(std::make_pair(0, s));
        while (not q.empty()) {
            const P& p = q.top();
            const T cost = p.first;
            const std::size_t v = p.second;
            q.pop();
            if (d[v] < cost) {
                continue;
            }
            for (const auto& e : m_table[v]) {
                if (d[e.to] > d[v] + e.cost) {
                    d[e.to] = d[v] + e.cost;
                    q.push(std::make_pair(d[e.to], e.to));
                }
            }
        }
    }

    void WarshallFloyd(std::vector<std::vector<T>>& d)
    {
        assert(d.size() == m_v);
        for (std::size_t i = 0; i < m_v; i++) {
            assert(d[i].size() == m_v);
            for (std::size_t j = 0; j < m_v; j++) {
                if (i == j) {
                    d[i][j] = 0;
                } else {
                    d[i][j] = INF;
                }
            }
            for (const auto& e : m_table[i]) {
                d[i][e.to] = std::min(e.cost, d[i][e.to]);  // For doubled-link
            }
        }
        for (std::size_t k = 0; k < m_v; k++) {
            for (std::size_t i = 0; i < m_v; i++) {
                for (std::size_t j = 0; j < m_v; j++) {
                         if (d[i][j] > d[i][k] + d[k][j] and d[i][k] < INF and d[k][j] < INF) {
                        d[i][j] = d[i][k] + d[k][j];
                    }
          }
            }
        }
    }

    std::size_t getV() const
    {
        return m_v;
    }

    std::size_t getE() const
    {
        return m_e;
    }

    const std::vector<std::vector<std::size_t>>& getEdge() const
    {
        return m_table;
    }

    std::vector<std::vector<std::size_t>>& getEdge()
    {
        return m_table;
    }

    const std::vector<std::vector<std::size_t>>& getReversedEdge() const
    {
        return m_reversed_table;
    }

    std::vector<std::vector<std::size_t>>& getReversedEdge()
    {
        return m_reversed_table;
    }

    static constexpr T INF = std::numeric_limits<T>::max() / 100;

private:
    void dfs_topo(const std::size_t s, std::vector<bool>& yet, std::vector<std::size_t>& st, std::size_t& pos) const
    {
        assert(s < m_v);
        assert(yet.size() == m_v);
        assert(st.size() == m_v);
        assert(pos < m_v);
        yet[s] = false;
        for (const auto& e : m_table[s]) {
            if (yet[e.to]) {
                dfs_topo(e.to, yet, st, pos);
            }
        }
        st[pos] = s;
        pos--;
    }

    void dfs1_scc(const std::size_t s, std::vector<std::size_t>& cmp, std::vector<std::size_t>& st, std::size_t& pos) const
    {
        assert(s < m_v);
        assert(cmp.size() == m_v);
        assert(st.size() == m_v);
        assert(pos < m_v);
        cmp[s] = 0;
        for (const auto& e : m_table[s]) {
            if (cmp[e.to]) {
                dfs1_scc(e.to, cmp, st, pos);
            }
        }
        st[pos] = s;
        pos--;
    }

    void dfs2_scc(const std::size_t s, const std::size_t index, std::vector<std::size_t>& cmp) const
    {
        assert(s < m_v);
        assert(index < m_v);
        assert(cmp.size() == m_v);
        cmp[s] = index;
        for (const auto& e : m_reversed_table[s]) {
            if (cmp[e.to] == INF) {
                dfs2_scc(e.to, index, cmp);
            }
        }
    };
    const std::size_t m_v;
    std::size_t m_e;
    std::vector<std::vector<Edge<T>>> m_table;
    std::vector<std::vector<Edge<T>>> m_reversed_table;
};

int main()
{
    std::size_t V, E;
    std::cin >> V >> E;
    Graph<long long> g{V};
    for (std::size_t i = 0; i < E; i++) {
        std::size_t s, t;
        long long c;
        std::cin >> s >> t >> c;
        g.addEdge(s, t, c);
    }
    std::vector<std::vector<long long>> d(V, std::vector<long long>(V));
    g.WarshallFloyd(d);
    for (std::size_t i = 0; i < V; i++) {
        if (d[i][i] < 0) {
            std::cout << "NEGATIVE CYCLE" << std::endl;
            return 0;
        }
    }

    for (std::size_t i = 0; i < V; i++) {
        for (std::size_t j = 0; j < V; j++) {
            if (d[i][j] != Graph<long long>::INF) {
                std::cout << d[i][j];
            } else {
                std::cout << "INF";
            }
            if (j == V - 1) {
                std::cout << std::endl;
            } else {
                std::cout << " ";
            }
        }
    }

    return 0;
}

Measured memory_bytes: 3632