Cookie-Loving Chunbae

Chunbae ate every cookie at home again today. When Siwon tells him about an event at a cookie shop, he decides to go.

The shop has $K$ cookies on a display shelf of $N$ cells. Cookie $i$ is in cell $X_i$ and costs $C_i$ won. The cookies are all in different positions.

Because the shop is running an event, if Chunbae buys cookie $i$, the shop gives him, for free, any cookies he wants among those whose distance from cookie $i$ is at most $R_i$. The distance between cookies $i$ and $j$ is $|X_i - X_j|$.

Chunbae is broke after buying a MacBook, and he wants to eat all $K$ cookies at the lowest cost. Find the minimum amount he must pay, by buying cookies or receiving them for free, to get all $K$ cookies.

The first line contains the shelf length $N$ and the number of cookies $K$, separated by a space. $(1 \le K \le N \le 100\,000)$

From the second line on, the next $K$ lines each contain $X_i$, $R_i$, and $C_i$, separated by spaces. $(1 \le X_i \le N, 0 \le R_i \le N, 1 \le C_i \le 1\,000)$

Print the minimum amount that must be paid to buy all cookies.