lines = $stdin.read
array = lines.split("\n")

#
# :u ノードのインデックス
# :k u の出次数
# :v u に隣接する頂点の番号
# :w 隣接する頂点への重み
# ---
# :visited 深さ優先探索用
# ---
# 閉路の判定のため深さ優先探索も実装してみる
#   深さ優先探索で親ノードへの戻り辺があれば、それは閉路である。トポロジカルソートでも検出できる。
#   Wikipedia - 閉路 より
#
INF  = 999999999
Node = Struct.new(:u, :k, :v, :w, :visited)

class Graph
  attr :nodes, :dist
  def initialize(n)
    @nodes = Array.new(n){ Node.new }
    @nodes = @nodes.map.with_index do |node,idx|
      node.u = idx
      node
    end
    @dist = Array.new(n).map{Array.new(n, 0)}
  end

  def add_graph_edge(u, v, w)
    #puts "#{u} -> #{v} (#{w})"
    if @nodes[u].v.nil?
      @nodes[u].v = [v]
      @nodes[u].w = {v=>w}
    elsif @nodes[u].v.is_a?(Array)
      @nodes[u].v << v
      @nodes[u].w = {v=>w}.merge(@nodes[u].w)
    else
      @nodes[u].v = [@nodes[u].v, v]
      @nodes[u].w = {v=>w}.merge(@nodes[u].w)
    end
    @nodes[u].k = if @nodes[u].v.is_a?(Array)
                    @nodes[u].v.length
                  else
                    1
                  end
  end

  def warshall_floyd()
    # initialize
    for i in 0...@nodes.length
      for j in 0...@nodes.length
        @dist[i][j] = if not @nodes[i].w.nil? and @nodes[i].w.has_key?(j)
                        @nodes[i].w[j]
                      else
                        Float::INFINITY
                      end
        @dist[i][j] = 0 if i==j
      end
    end

    # calc
    for k in 0...@nodes.length
      for i in 0...@nodes.length
        for j in 0...@nodes.length
          if @dist[i][j] > @dist[i][k] + @dist[k][j]
            @dist[i][j] = @dist[i][k] + @dist[k][j]
          end
        end
      end
    end
  end

  def collect_weight(node_idxs)
    # p node_idxs
    ans = 0
    node_idxs.each_cons(2) do |ns|
      #p ns
      #p @nodes[ns.first].w
      #p ns.last
      ans += @nodes[ns.first].w[ns.last].to_i
    end
    p ans
    ans
  end

  def has_negative_cycle?()
    @nodes.any? do |node|
      @nodes = @nodes.map{|n| n.visited = false; n}

      rec,weight = dfs(node.u, node.u)
      rec = rec.uniq
      #p rec
      #p weight
      ans = rec.any? do |arr|
        not @nodes[arr.last].v.nil?               \
          and @nodes[arr.last].v.include?(node.u) \
          and @nodes[arr.last].w.to_a.first.last < 0
      end
      #puts "ans = #{ans}"
      ans
    end
  end

  def dfs(start = 0, init = 0, history = [], rec = [], weight = 0)
    #puts "  start visit = #{@nodes[start].to_s}"
    @nodes[start].visited = true
    history << start

    return rec,weight if @nodes[start].v.nil?

    for i in @nodes[start].v
      if @nodes[i].visited
        # 探索終わり
        rec << history
      else
        # そうでない場合さらに探索
        weight += @nodes[start].w[i]
        dfs(i, init, history, rec, weight)
      end
    end
    #puts "  end visited = #{@nodes[start].to_s}"
    return rec,weight
  end
end

V,E = array[0].split(" ").map(&:to_i)
graph = Graph.new(V)

array[1..E].each do |s|
  s,t,d = s.split(" ").map(&:to_i)
  graph.add_graph_edge(s,t,d)
end

# execute WarshallFloyd !
graph.warshall_floyd()

if graph.has_negative_cycle?
  puts "NEGATIVE CYCLE"
else
  graph.dist.each do |d|
    puts d.map{|d| if d == Float::INFINITY; "INF" else d end}.join(" ")
  end
end
