Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappush, heappop
INF = 10 ** 20
def search(item_lst):
  dp = [[INF] * 101 for _ in range(101)]
  dp[0][0] = 0
  que = []
  heappush(que, (0, 0, 0))
  while que:
    score, a, e = heappop(que)
    for da, de in item_lst[e]:
      na, ne = min(d, a + da), min(100, e + de)
      if na == d:
        print(score + 1)
        return True

      if dp[na][ne] > score + 1:
        dp[na][ne] = score + 1
        heappush(que, (score + 1, na, ne))
  
  print("NA")
  return False

while True:
  d, n = map(int, input().split())
  if d == 0:
    break
  item_lst = [[] for _ in range(101)]
  for _ in range(n):
    a, e, r = map(int, input().split())
    for i in range(r, 101):
      item_lst[i].append((a, e))
  search(item_lst)


Fixed submission:
from heapq import heappush, heappop
INF = 10 ** 20

def search(item_lst, d):
  visited = {}
  visited[(0, 0)] = True
  que = []
  heappush(que, (0, 0, 0))
  while que:
    score, a, e = heappop(que)
    for da, de in item_lst[e]:
      na = a + da
      if na >= d:
        print(score + 1)
        return True
      ne = e + de
      if ne > 100:
        ne = 100
      
      if (na, ne) not in visited:
        visited[(na, ne)] = True
        heappush(que, (score + 1, na, ne))
  
  print("NA")
  return False

def main():
  while True:
    d, n = map(int, input().split())
    if d == 0:
      break
    item_lst = [[] for _ in range(101)]
    for _ in range(n):
      a, e, r = map(int, input().split())
      for i in range(r, 101):
        item_lst[i].append((a, e))
    search(item_lst, d)
main()

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappush, heappop
INF = 10 ** 20

def search(item_lst):
  visited = {}
  visited[(0, 0)] = True
  que = []
  heappush(que, (0, 0, 0))
  while que:
    score, a, e = heappop(que)
    for da, de in item_lst[e]:
      na, ne = min(d, a + da), min(100, e + de)
      if na == d:
        print(score + 1)
        return True

      if (na, ne) not in visited:
        visited[(na, ne)] = True
        heappush(que, (score + 1, na, ne))
  
  print("NA")
  return False

while True:
  d, n = map(int, input().split())
  if d == 0:
    break
  item_lst = [[] for _ in range(101)]
  for _ in range(n):
    a, e, r = map(int, input().split())
    for i in range(r, 101):
      item_lst[i].append((a, e))
  search(item_lst)


Fixed submission:
from heapq import heappush, heappop
INF = 10 ** 20

def search(item_lst, d):
  visited = {}
  visited[(0, 0)] = True
  que = []
  heappush(que, (0, 0, 0))
  while que:
    score, a, e = heappop(que)
    for da, de in item_lst[e]:
      na = a + da
      if na >= d:
        print(score + 1)
        return True
      ne = e + de
      if ne > 100:
        ne = 100
      
      if (na, ne) not in visited:
        visited[(na, ne)] = True
        heappush(que, (score + 1, na, ne))
  
  print("NA")
  return False

def main():
  while True:
    d, n = map(int, input().split())
    if d == 0:
      break
    item_lst = [[] for _ in range(101)]
    for _ in range(n):
      a, e, r = map(int, input().split())
      for i in range(r, 101):
        item_lst[i].append((a, e))
    search(item_lst, d)
main()