30417번 - 쿠키를 좋아하는 춘배

문제

오늘도 하루 만에 집에 있는 모든 쿠키를 다 먹은 춘배는 시원에게 쿠키 가게에서 이벤트를 한다는 이야기를 듣고 쿠키 가게에 가기로 했다.

쿠키 가게에는 $N$개의 칸으로 이루어진 진열대 위에 $K$개의 쿠키가 놓여 있다. $i$번 쿠키는 $X_i$번째 칸에 있고 가격은 $C_i$원이다. 단, 과자의 위치는 서로 다르다.

시원이의 쿠키 가게는 이벤트를 하고 있기 때문에 $i$번 쿠키를 구매하면 $i$번 쿠키와 거리가 $R_i$ 이하인 쿠키 중 원하는 쿠키들을 전부 무료로 준다. 두 쿠키 $i$와 $j$사이의 거리는 $\mid X_i - X_j \mid$와 같다.

맥북을 사느라 가난해진 춘배는 최소의 비용으로 모든 $K$개의 쿠키를 전부 먹고 싶었다. 춘배가 쿠키를 구매하거나 무료로 받아 모든 쿠키를 받기 위해 최소 얼마의 금액을 지불해야 되는지 구해보자.

입력

첫째 줄에 진열대의 길이 $N$과 쿠키의 개수 $K$가 공백으로 구분되어 주어진다.$(1 \le K \le N \le 100,000円)$

둘째 줄부터 $K$개의 줄에 걸쳐 $X_i,ドル $R_i,ドル $C_i$가 공백으로 구분되어 주어진다. $(1 \le X_i \le N, 0 \le R_i \le N, 1 \le C_i \le 1,000円)$

출력

모든 쿠키를 구매하기 위해 지불해야 하는 최소 금액을 출력한다.

제한

힌트