Tèo hiện đang chơi một trò chơi nông trại trên điện thoại. Trong trò chơi có \(N\) hoạt động được đánh số từ \(1\) đến \(N\), mỗi hoạt động là một việc cần làm theo trình tự (trồng cây, chăm bón, thu hoạch, bán sản phẩm). Sau khi hoàn thành hoạt động \(u\), Tèo có thể chọn chuyển sang làm hoạt động \(v\) (với \(v > u\) theo thứ tự thời gian). Mỗi cách chuyển từ \(u\) sang \(v\) mang về một khoản lợi nhuận là \(w\) đồng xu trong game:

• \(w > 0\): chuyển sang \(v\) giúp Tèo kiếm thêm tiền.
• \(w = 0\): không thay đổi số dư.
• \(w < 0\): chuyển sang \(v\) mất một ít tiền (do tốn phí mua hạt giống, sửa chuồng...).

Theo thiết kế của trò chơi, mọi cách chuyển đều đi theo thứ tự thời gian từ hoạt động sớm sang hoạt động muộn, nên trình tự chuyển đổi đảm bảo không tạo vòng khép kín.

Tèo muốn bắt đầu từ hoạt động \(1\) và kết thúc ở hoạt động \(N\) để nhận thưởng cuối game. Hãy giúp Tèo tính tổng lợi nhuận lớn nhất có thể đạt được.

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

• Dòng đầu chứa hai số nguyên \(N\) và \(M\) (\(1 \le N \le 10^5\), \(0 \le M \le 2 \cdot 10^5\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u, v, w\) mô tả một bước chuyển từ hoạt động \(u\) sang hoạt động \(v\) mang lại lợi nhuận \(w\) (\(-10^9 \le w \le 10^9\), \(u \ne v\)).
• Đảm bảo: luôn có ít nhất một cách đi từ hoạt động \(1\) đến hoạt động \(N\).

Định dạng đầu ra

• Một số nguyên duy nhất là tổng lợi nhuận lớn nhất từ hoạt động \(1\) đến hoạt động \(N\).

Ví dụ

Input:

5 6
1 2 5
1 3 -3
2 4 4
3 4 -1
4 5 2
2 5 -2

Output:

11

Giải thích: Đường đi \(1 \to 2 \to 4 \to 5\) cho tổng \(5 + 4 + 2 = 11\) là lớn nhất.

Ràng buộc

• \(1 \le N \le 10^5\)
• \(0 \le M \le 2 \cdot 10^5\)
• \(-10^9 \le w \le 10^9\)
• Luôn có ít nhất một cách đi từ \(1\) đến \(N\).
• Trình tự chuyển đổi đảm bảo không tạo vòng khép kín.