Một bệnh viện cần được trực cấp cứu liên tục trong ~n~ giờ để đảm bảo luôn sẵn sàng tiếp nhận bệnh nhân. Thời điểm bắt đầu được tính từ ~0~. Bệnh viện có danh sách ~m~ bác sĩ có thể phân công trực. Các bác sĩ được đánh số từ ~1~ đến ~m~. Bác sĩ thứ ~i~ trực từ thời điểm ~s_i~ đến thời điểm ~t_i~ ~(0 \le s_i < t_i \le n)~ với chi phí trực là ~c_i~.

Yêu cầu: Hãy chọn một số bác sĩ sao cho: Tại mọi thời điểm trong khoảng từ ~0~ đến ~n~, luôn có ít nhất một bác sĩ trực và tổng chi phí trực là nhỏ nhất. Dữ liệu đảm bảo luôn tồn tại phương án hợp lệ.

Input

• Dòng đầu tiên chứa ~2~ số nguyên ~n~ và ~m~ ~(0 < n, m \le 100)~

• ~m~ dòng tiếp theo, mỗi dòng chứa ba số nguyên không âm ~s_i, t_i~ và ~c_i~ ~(0 \le s_i < t_i \le n; 0 < t_i \le 10^9)~

Output

Một số nguyên là chi phí thuê nhỏ nhất (dữ liệu được cho đảm bảo luôn có kết quả).

Sample Input 1

9 5
0 5 25
1 3 18
3 7 21
4 6 38
7 9 20

Sample Output 1

66

Notes

Chọn các bác sĩ trực trong các khung giờ:

• ~0-5~ (chi phí ~25~)

• ~3-7~ (chi phí ~21~)

• ~7-9~ (chi phí ~20~)

Tổng chi phí trực là ~66~ và bệnh viện luôn có bác sĩ trực cấp cứu.