High Score — Eolymp

Input

The first line has two integers $n (1 \leq n \leq 2500)$ n\:(1 \le n \le 2500) and $m (1 \leq m \leq 5000)$ m\:(1 \le m \le 5000): the number of rooms and tunnels. The rooms are numbered $1, 2, \dots, n$ 1, 2, \dots , n.

Then, there are $m$ lines describing the tunnels. Each line has three integers $a$ , $b (1 \leq a, b \leq n)$ b\:(1 \le a, b \le n) and $x (- 1 0^{9} \leq x \leq 1 0^{9})$ x\:(−10^9 \le x \le 10^9): the tunnel starts at room $a$ , ends at room $b$ , and it increases your score by $x$ . All tunnels are one-way tunnels.

You can assume that it is possible to get from room $1$ to room $n$ .

Output

Print one integer: the maximum score you can get. However, if you can get an arbitrarily large score, print $- 1$ .

Examples

Example 1

Loading