n, m = gets.split.map(&:to_i)
a = Array.new(n).map { Array.new(n, Float::INFINITY) }
(0..n-1).each {|i| a[i][i] = 0 }
m.times do
  i, j, d = gets.split.map(&:to_i)
  a[i][j] = d if d < a[i][j]
end

(0..n-1).each do |k|
  (0..n-1).each do |i|
    (0..n-1).each do |j|
      x = a[i][k] + a[k][j]
      a[i][j] = x if x < a[i][j]
    end
  end
end

catch :exit do
  (0..n-1).each do |k|
    (0..n-1).each do |i|
      (0..n-1).each do |j|
        x = a[i][k] + a[k][j]
        if x < a[i][j]
          puts 'NEGATIVE CYCLE'
          throw :exit
        end
      end
    end
  end

  a.each do |row|
    puts row.map {|x| x == Float::INFINITY ? 'INF' : x } * ' '
  end
end
