쿠키를 좋아하는 춘배

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

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

가게가 이벤트 중이어서, $i$번 쿠키를 구매하면 $i$번 쿠키와의 거리가 $R_i$ 이하인 쿠키 중 원하는 쿠키를 전부 무료로 준다. 두 쿠키 $i$와 $j$ 사이의 거리는 $|X_i - X_j|$이다.

맥북을 사느라 가난해진 춘배는 $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)$

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