Bạn đang chơi một trò chơi 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 bạn đi qua có thể cho bạn một số điểm ~x~. Mọi đường hầm đều là đường một chiều và có thể đi qua nhiều lần.

Nhiệm vụ của bạn là đi từ phòng 1 đến phòng thứ ~N~. Số điểm tối đa mà bạn có thể nhận được là bao nhiêu?

Input

Dòng đầu tiên chứa 2 số nguyên ~N~ và ~M~: số phòng và số đường hầm có trong trò chơi ~M~ dòng tiếp theo, mỗi dòng chứa 3 số nguyên ~u, v, w~: biểu diễn có đường hầm đi từ phòng ~u~ đến phòng ~v~ và cho bạn ~w~ điểm

Output

Gồm một số nguyên là kết quả của bài toán. Nếu số điểm bạn nhận được là một số nguyên lớn vô hạn, in ra -1

Giới hạn

~1 <= N <= 2500~

~1 <= M <= 5000~

~1 <= u, v <= N~

~-10^9 <= w <= 10^9~

Test mẫu

Input

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

Output

5