Viện bảo tàng X tổ chức cuộc trưng bày giới thiệu một số bức tranh của danh họa Leonard de Vinci. Những bức tranh của danh họa thường là mục tiêu của nhiều tổ chức trộm cắp chuyên nghiệp. Vì thế, Ban giám đốc bảo tàng cần giải quyết vấn đề bảo vệ an toàn cho các bức tranh độc nhất vô nhị này. Theo kế hoạch, cuộc triển lãm sẽ diễn ra trong vòng ~n~ giờ. Thời điểm bắt đầu triển lãm được tính bằng 0. Có ~m~ vệ sĩ nghiệp vụ cao có thể thuê để canh gác những bức tranh. Để đơn giản, các vệ sĩ này được đánh số thứ tự từ 1 đến ~m~. Vệ sĩ ~i~ chấp nhận đứng canh trong khoảng thời gian từ thời điểm ~s_i~ đến thời điểm ~t_i~ (~0 \le s_i < t_i \le 10^5~) với tiền công là ~c_i~ (với ~i = 1, 2, \dots, n~).

Yêu cầu: Hãy giúp Ban giám đốc lựa chọn thuê các vệ sĩ nào trong số ~m~ vệ sĩ để bất cứ thời điểm nào diễn ra triển lãm luôn có ít nhất một vệ sĩ đứng canh, đồng thời tổng chi phí thuê trả cho các vệ sĩ đó là nhỏ nhất.

Input

• Dòng đầu ghi 2 số nguyên dương ~n~ và ~m~ (~n, m \le 10^5~).
• Dòng thứ ~i~ trong ~m~ dòng tiếp theo chứa ba số nguyên không âm ~s_i, t_i, c_i~ (~0 \le c_i < 10^5~). Các số trên một dòng cách nhau bởi một khoảng trắng. Dữ liệu đảm bảo luôn có lời giải.

Output

• Ghi ra một số nguyên dương duy nhất là tổng chi phí nhỏ nhất để thuê các vệ sĩ.

Sample Input 1

9 7
0 5 30
1 3 18
4 7 21
4 8 38
6 9 20
5 8 22
8 9 29

Sample Output 1

71