Problem C: Warping Girl

Problem

会津魔法学校は, 魔法を使える者が集まる学校である. その学校の生徒の一人であるハルカは, 魔法陣の上でワープの魔法を使う事ができる.

彼女の家から学校には, 長さ L の一直線状の道がある. また, この道には所々魔法陣が描かれている.
彼女は毎日この道を使って学校に通っているため, できるだけ短い時間で学校に辿り着きたいと思っている.

そこでプログラマーであるあなたは, 彼女に学校まで行くときにかかる最小の時間を教えてあげることにした.

ハルカは, 1 分で距離 1 だけ歩いて先に進むことができる ( ＊戻ることはできない)．また, ワープの魔法陣が書いてある位置 P_i で魔法を唱えることで, P_i からちょうど D_i だけ進んだ場所に T_i 分で移動することができる. 移動先に魔法陣がある場合も, 連続してワープ魔法を使用することができる.

彼女の家の位置は 0、学校の位置は L である.

Input

L n
P1 D1 T1
P2 D2 T2
.
.
Pn Dn Tn

１行目に道の長さ L, 魔法陣の数 n が与えられる. 次に n 個の魔法陣の状態が与えられる. P_i は i 番目の魔法陣がある位置, D_i は i 番目の魔法陣からワープする距離, T_i は i 番目の魔法陣を使ってワープしたときにかかる時間を表す.

Constraints

入力は以下の条件を満たす.

• 与えられる数は全て整数である
• 1 ≤ L ≤ 10⁹
• 0 ≤ n ≤ min(10³, L) (min はA, B の小さい方を表す)
• 0 ≤ P_i ≤ L - 1
• 0 ≤ D_i ≤ L - P_i
• 0 ≤ T_i ≤ 10³
• P_i ≠ P_j

Output

学校に辿り着くための最小の時間を一行に出力せよ.

Sample Input 1

10 3
2 2 1
4 2 1
8 1 1

Sample Output 1

8

Sample Input 2

10 2
2 3 1
3 5 1

Sample Output 2

6

Sample Input 3

1 0

Sample Output 3

1