#Warhall-Floyd Algorighm
class Edge
  attr_accessor :s, :t, :d
  def initialize(s, t, d)
    @s = s
    @t = t
    @d = d
  end
end

v, e = gets.split.map(&:to_i)

m = Array.new(v){Array.new(v){1.0/0.0}}

edges = []
e.times{|i|
  s, t, d = gets.split.map(&:to_i)
  m[s][t] = d
  edges[i] = Edge.new(s, t, d)
}
v.times{|i|
  m[i][i] = 0
}

v.times{|k|
  v.times{|i|
    v.times{|j|
      m[i][j] = m[i][k] + m[k][j] if m[i][j] > m[i][k] + m[k][j]
    }
  }
}

v.times{|i|
  edges.each{|edge|
    if m[i][edge.s] + edge.d < m[i][edge.t]
      puts "NEGATIVE CYCLE"
      exit
    end
  }
}

v.times{|i|
  v.times{|j|
    m[i][j] = "INF" if m[i][j] == 1.0 / 0.0
  }
  puts m[i].join(" ")
}