Marisa có \(n\) cây táo. Cô muốn hái hết táo từ cả \(n\) cây, nhưng số lượng cây lại quá nhiều. Chính vì thế, cô đã thuê Nitori giúp cô hái táo.

Nitori có \(q\) dịch vụ khác nhau. Dịch vụ \(i\) có giá là \(c_i\), Nitori sẽ thu hoạch toàn bộ các cây táo đánh số từ \(l_i\) đến \(r_i\). Marisa muốn biết chi phí rẻ nhất để thu hoạch toàn bộ \(n\) cây táo. Các bạn giúp cô nhé!

Input

• Dòng đầu tiên gồm 2 số nguyên \(n, q\).
• \(q\) dòng tiếp theo, mỗi dòng gồm 3 số nguyên \(l_i, r_i,c_i\), một gói dịch vụ.

Output

• In ra chi phí nhỏ nhất. Nếu không có cách nào để hái toàn bộ các cây, in ra -1.

Điều kiện

• \(1 \le n, q\le 10^5\).
• \(1 \le l_i, r_i \le n\).
• \(1 \le c_i \le 10^9\).

Ví dụ

Input:

5 3
1 4 2
5 5 3
2 5 1

Output:

3