require 'set'

def bfs(start_node, extra = nil)
    return 0 if start_node.is_goal?(extra)
    reached = Set[start_node]
    dist = 1
    queue = [start_node]
    until queue.empty?
        next_queue = []
        until queue.empty?
            node = queue.shift
            node.each_next_node(extra) do |next_node|
                return dist if next_node.is_goal?(extra)
                next if reached.include?(next_node)
                reached << next_node
                next_queue << next_node
            end
        end
        dist += 1
        queue = next_queue
    end
    return nil
end

class Array
    def is_goal?(weapons)
        self[0] <= 0
    end

    def each_next_node(weapons)
        d, t = self
        weapons.each do |a, e, r|
            next if r > t
            yield [d - a, t + e]
        end
    end
end

loop do
    d, n = gets.split.map(&:to_i)
    break if n == 0
    weapons = (1..n).map { gets.split.map(&:to_i) }
    puts bfs([d, 0], weapons) || 'NA'
end

