Điểm thưởng tối đa

Bối cảnh và bài toán

Một hành trình từ nút 1 tới n đi qua các cung có thể cộng hoặc trừ điểm. Có thể đi qua một cung nhiều lần.

Yêu cầu

Tìm điểm tối đa có thể đạt. Nếu có thể làm điểm tăng vô hạn mà vẫn tới n, in -1.

Input

Dòng đầu n, m; tiếp theo m cạnh có hướng u, v, x.

Output

In điểm tối đa hoặc -1.

Ràng buộc

• 1 <= n <= 2500
• 1 <= m <= 5000
• -10^9 <= x <= 10^9 ## Chấm điểm | Subtask | Điểm | Điều kiện | Official tests | |---|---:|---|---| | S1 | 40 | n <= 100, m <= 300 | 01–08 | | S2 | 60 | Không có ràng buộc bổ sung | 09–20 |

Ví dụ 1

Input

4 5
1 2 3
2 4 -1
1 3 -2
3 4 7
1 4 4

Output

5

Giải thích. Chu trình dương chỉ làm đáp án vô hạn khi nằm trên một hành trình có thể đi từ 1 rồi tới n.

Ví dụ 2

Input

3 3
1 2 1
2 2 1
2 3 1

Output

-1

Giải thích. Chu trình dương chỉ làm đáp án vô hạn khi nằm trên một hành trình có thể đi từ 1 rồi tới n.

Thông tin bài tập

Nguồn: Phỏng theo / Adapted from CSES High Score. Bản FULLHOUSE DEV đã biên tập lại bối cảnh/format theo phạm vi khóa học.