Nhà máy lắp ráp ô tô của bác Tài có \(N\) công đoạn sản xuất, được đánh số từ \(1\) đến \(N\). Giữa các công đoạn có những băng chuyền một chiều: từ công đoạn \(u\) đến công đoạn \(v\) mất đúng \(w\) phút để chuyển tiếp (\(u < v\)). Dây chuyền bắt buộc phải xuất phát từ công đoạn \(1\) và kết thúc ở công đoạn \(N\). Bác Tài muốn tính tổng thời gian dài nhất có thể cho một hành trình dọc dây chuyền như vậy, giúp đánh giá năng suất cao nhất nếu các bước đều diễn ra suôn sẻ.

Hãy giúp bác Tài tính tổng thời gian dài nhất. Nếu không có đường đi từ \(1\) đến \(N\) thì in ra \(-1\).

Định dạng đầu vào

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\) (\(2 \le N \le 10^5\), \(1 \le M \le 2 \times 10^5\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u\), \(v\) và \(w\) (\(1 \le u < v \le N\), \(-10^5 \le w \le 10^5\)).

Định dạng đầu ra

• In ra tổng thời gian lớn nhất hoặc \(-1\) nếu từ \(1\) không đến được \(N\).

Ví dụ

Input:

4 4
1 2 3
1 3 5
2 4 2
3 4 4

Output:

9

Ràng buộc

• \(20\%\) số điểm ứng với \(N \le 100\).
• \(30\%\) số điểm ứng với \(N \le 5000\).
• \(50\%\) số điểm còn lại không có ràng buộc gì thêm.