Chương trình nghệ thuật

Trong một chương trình nghệ thuật diễn ra liên tục trong \(n\) giờ (tính từ thời điểm \(0\) đến thời điểm \(n\)), công ty có danh sách \(m\) nghệ sĩ có thể thuê để biểu diễn.

Nghệ sĩ thứ \(i\) biểu diễn 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í thuê là \(c_i\) \((0\le c_i \le 10^6)\).

Hãy chọn một số nghệ sĩ sao cho tại mọi thời điểm trong khoảng \([0,n]\) luôn có ít nhất một nghệ sĩ đang biểu diễn, và tổng chi phí thuê là nhỏ nhất.

Dữ liệu được cho đảm bảo luôn tồn tại phương án.

Input

Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) \((1\le n,m\le 400)\).

\(m\) dòng tiếp theo, mỗi dòng chứa ba số nguyên không âm \(s_i, t_i, c_i\).

Output

In ra một số nguyên là tổng chi phí thuê nhỏ nhất.

Scoring

• Subtask 1 (30%): \(n,m \le 50\).
• Subtask 2 (30%): \(n,m \le 200\).
• Subtask 3 (40%): \(n,m \le 400\).

Sample Input 1

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

Sample Output 1

66