Bạn chơi một trò chơi gồm n phòng và m hầm. Điểm số ban đầu là 0, và mỗi khi đi qua một hầm điểm số của bạn thay đổi thêm một giá trị x (x có thể dương hoặc âm). Bạn có thể đi qua một hầm nhiều lần.

Nhiệm vụ của bạn là đi từ phòng 1 tới phòng n. Hỏi điểm số lớn nhất bạn có thể đạt được?

Input:

Dòng đầu chứa hai số nguyên n và m: số phòng và số hầm. Các phòng được đánh số 1, 2, ..., n.

Tiếp theo là m dòng mô tả các hầm. Mỗi dòng gồm ba số nguyên a b x: hầm bắt đầu ở phòng a, kết thúc ở phòng b, và khi đi qua hầm này điểm số thay đổi thêm x. Tất cả các hầm là một chiều.

Giả sử luôn có đường đi từ phòng 1 tới phòng n.

Output:

In ra một số nguyên: điểm số lớn nhất có thể đạt được.

Nếu bạn có thể đạt điểm tùy ý lớn (không bị chặn, tức là có chu trình tích lũy dương mà có thể đi từ 1 tới n qua chu trình đó), in -1.

Ràng buộc:

~1 \le n \le 2500~

~1 \le m \le 5000~

~1 \le a,b \le n~

~-10^9 \le x \le 10^9~

Ví dụ :

Input:

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

Output:

5