Điểm Số Trên Hành Trình

Có $n$ đỉnh được đánh số từ $1$ đến $n$ và $m$ cạnh có hướng. Khi đi qua một cạnh, bạn nhận thêm số điểm ghi trên cạnh đó; số điểm này có thể âm, bằng $0$ hoặc dương.

Bạn bắt đầu tại đỉnh $1$ với $0$ điểm và cần kết thúc tại đỉnh $n$. Một cạnh có thể được đi qua nhiều lần, vì vậy hành trình được phép lặp lại đỉnh và cạnh. Dữ liệu bảo đảm luôn có ít nhất một hành trình từ $1$ tới $n$.

Hãy tìm số điểm lớn nhất có thể đạt được khi tới $n$. Nếu có thể làm tổng điểm tăng lớn tùy ý rồi vẫn đi tiếp tới $n$, hãy in $-1$.

Khi $n=1$, hành trình rỗng với $0$ điểm là hợp lệ. Tuy nhiên, nếu từ đỉnh $1$ có thể đi qua một chu trình làm tăng điểm và quay về một vị trí còn tới được đỉnh $n$, đáp án vẫn là không bị chặn.

Input

• Dòng đầu chứa hai số nguyên $n$ và $m$.
• Mỗi trong $m$ dòng tiếp theo chứa ba số nguyên $a,b,x$, biểu thị một cạnh có hướng từ $a$ tới $b$; đi qua cạnh đó làm tổng điểm thay đổi thêm $x$.

Output

• Nếu tổng điểm có thể tăng không giới hạn, in $-1$.
• Ngược lại, in tổng điểm lớn nhất hữu hạn của một hành trình từ $1$ tới $n$. Giá trị hữu hạn này có thể là số âm.

Constraints

• $1\le n\le 2500$.
• $1\le m\le 5000$.
• $1\le a,b\le n$.
• $-10^9\le x\le 10^9$.
• Cạnh tự khuyên và nhiều cạnh có cùng hai đầu mút đều được phép.
• Luôn có đường đi có hướng từ $1$ tới $n$.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n\le 80,m\le 200$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

4 5
1 2 4
2 4 -1
1 3 -2
3 4 8
2 3 1

13

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

-1