Cho đồ thị gồm ~N~ đỉnh, ban đầu đồ thị không có cạnh nối. Thực hiện ~M~ thao tác trên đồ thị như sau:

• Thao tác thứ ~i~ (~1 \le i \le M~) gồm ba số nguyên ~L_i~, ~R_i~ và ~C_i~ (~L_i < R_i~) : Với mỗi cặp đỉnh ~(u,v)~ thỏa mãn ~L_i \le u < v \le R_i~, thêm cạnh nối giữa hai đỉnh ~u~ và ~v~ với độ dài ~C_i~.

Hỏi sau khi thực hiện tất cả ~M~ thao tác, độ dài đường đi ngắn nhất từ đỉnh ~1~ đến đỉnh ~N~ là bao nhiêu ?

Lưu ý rằng đồ thị sau khi thực hiện các thao tác có thể là đa đồ thị.

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~M~ là số đỉnh và số thao tác (~2 \le N \le 10^9~, ~1 \le M \le 10^5~).
• ~M~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên ~L_i~, ~R_i~ và ~C_i~ mô tả thao tác thứ ~i~ (~1 \le L_i < R_i \le N~, ~1 \le C_i \le 10^9~).

Output

• In ra độ dài đường đi ngắn nhất từ đỉnh ~1~ đến đỉnh ~N~ sau khi thực hiện tất cả các thao tác. Nếu không có đường đi từ đỉnh ~1~ đến đỉnh ~N~, in ra ~-1~.

Examples

Sample Input 1

4 2
1 3 2
3 4 5

Sample Output 1

7

Sample Input 2

4 2
1 2 2
3 4 1

Sample Output 2

-1

Scoring

• Subtask ~1~ với ~20\%~ số điểm: ~N,M \le 100~
• Subtask ~2~ với ~30\%~ số điểm: ~N \le 10^5~, ~R_i-L_i \le 3~ với mọi ~1 \le i \le M~
• Subtask ~3~ với ~30\%~ số điểm: ~N \le 10^5~
• Subtask ~4~ với ~20\%~ số điểm: Không có ràng buộc gì thêm

Notes

• Ở ví dụ đầu tiên, sau khi thực hiện tất cả các thao tác, đồ thị được xây dựng như sau:

• Ở ví dụ thứ hai, không tồn tại đường đi từ đỉnh ~1~ đến đỉnh ~4~ trong đồ thị sau: