Điểm cao nhất

Là một nhân viên giỏi trong lĩnh vực phân tích dữ liệu, FullHouse Dev được giao nhiệm vụ phân tích một trò chơi đặc biệt. Họ cần tính toán điểm số tối đa có thể đạt được khi di chuyển qua các phòng được kết nối bởi các đường hầm.

Bài toán

Trò chơi gồm \(n\) phòng và \(m\) đường hầm. Điểm số ban đầu là 0, và mỗi khi đi qua một đường hầm, điểm số sẽ tăng thêm \(x\) (x có thể là số dương hoặc âm). Bạn có thể đi qua một đường hầm nhiều lần. Nhiệm vụ là đi từ phòng 1 đến phòng \(n\) và đạt được điểm số cao nhất có thể.

INPUT FORMAT:

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\): số lượng phòng và số lượng đường hầm. Các phòng được đánh số từ \(1\) đến \(n\).
• \(m\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(a\), \(b\) và \(x\): đường hầm bắt đầu từ phòng \(a\), kết thúc ở phòng \(b\), và làm tăng điểm số thêm \(x\). Tất cả đường hầm đều là một chiều.

OUTPUT FORMAT:

• In ra một số nguyên: điểm số cao nhất có thể đạt được. Tuy nhiên, nếu có thể đạt được điểm số vô hạn, in ra -1.

Ràng buộc:

• \(1 \leq n \leq 2500\)
• \(1 \leq m \leq 5000\)
• \(1 \leq a,b \leq n\)
• \(-10^9 \leq x \leq 10^9\)

Ví dụ

INPUT

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

OUTPUT

5

Giải thích

Có thể đạt được điểm số 5 bằng cách đi theo đường: 1 → 2 → 4 (3 + (-1) = 2) hoặc 1 → 3 → 4 (-2 + 7 = 5) hoặc đi thẳng từ 1 → 4 (4). Trong đó, đường đi 1 → 3 → 4 cho điểm số cao nhất là 5.