Mô tả bài toán: Tối đa hóa điểm trong trò chơi qua các phòng

Bạn đang chơi một trò chơi gồm n phòng và m đường hầm. Điểm ban đầu của bạn là 0, và mỗi đường hầm tăng hoặc giảm điểm của bạn một giá trị ~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ụ của bạn là:

1. Đi từ phòng 1 đến phòng ~n~.
2. Tối đa hóa tổng điểm mà bạn có thể đạt được.
3. Nếu có thể đạt được số điểm vô hạn, in ra ~-1~.

Input:

• 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.
• Tiếp theo có m dòng, mỗi dòng chứa ba số nguyên a, b, và x:
  • ~a~: phòng bắt đầu của đường hầm.
  • ~b~: phòng kết thúc của đường hầm.
  • ~x~: điểm cộng thêm khi đi qua đường hầm từ ~a~ đến ~b~.

Mỗi đường hầm là đường hầm một chiều.

Bạn có thể giả định rằng luôn có thể đi từ phòng 1 đến phòng ~n~.

Output:

• In ra một số nguyên:
  • Điểm tối đa bạn có thể đạt được khi đi từ phòng 1 đến phòng ~n~.
  • Nếu có thể đạt được số điểm 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~

Input:

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

Output:

5

Input:

3 3
1 2 100
2 3 100
3 2 1

Output:

-1