l, n = gets.chomp.split.map(&:to_i)
hsh, arr, arr2 = Hash.new{|h, k| h[k] = []}, [0, l], {}
n.times{
    p, d, t = gets.chomp.split.map(&:to_i)
    hsh[p] << [p + d, t]
    arr << p
    arr << p + d    
}
arr.sort!.uniq!
arr.each_with_index{|p, i| arr2[p] = i}

dp = [0]
hsh[0].each{|d, t| dp[arr2[d]] = t if dp[arr2[d]].nil? || dp[arr2[d]] > t}
1.upto(arr.length - 1){|i|
    temp = dp[i - 1] + arr[i] - arr[i - 1]
    dp[i] = temp if dp[i].nil? || dp[i] > temp
    hsh[arr[i]].each{|d, t| dp[arr2[d]] = dp[i] + t if dp[arr2[d]].nil? || dp[arr2[d]] > dp[i] + t}
}
puts dp.last
