Bạn chơi một trò chơi gồm \(n\) căn phòng và \(m\) đường hầm. Số điểm ban đầu của bạn là \(0\), và mỗi đường hầm tăng số điểm của bạn thêm \(x\) mà trong đó \(x\) có thể dương hoặc âm. Bạn có thể đi qua một đường hầm vài lần.

Nhiệm vụ của bạn là đi bộ từ phòng \(1\) đến phòng \(n\). Số điểm tối đa mà bạn có thể đạt được là bao nhiêu?

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(m\): số lượng phòng và đường hầm. Các phòng được đánh số \(1, 2, \ldots, n\).
• Sau đó, có \(m\) dòng mô tả các đường hầm. Mỗi dòng có ba số nguyên \(a\), \(b\) và \(x\): đường hầm bắt đầu tại phòng \(a\), kết thúc tại phòng \(b\), và tăng số điểm của bạn thêm \(x\). Tất cả đường hầm đều 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 một số nguyên: số điểm lớn nhất bạn có thể đạt được. Tuy nhiên, nếu bạn có thể đạt được số điểm lớn tùy ý, hãy in \(−1\).

Constraints

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

Example

Sample input

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

Sample output

5