Problem Statement

Nafmo is about to start playing a game consisting of $N$ dungeons.
The dungeons are numbered from $1$ to $N$, and clearing dungeon $i (1 \leq i \leq N)$ takes $A_i$ hours.
In addition, there are $M$ one-way roads between dungeons, numbered from $1$ to $M$. Road $j (1 \leq j \leq M)$ is a one-way road from dungeon $a_j$ to dungeon $b_j$, and traveling along it takes $c_j$ hours.
When dungeon $i$ has been cleared, if there are roads starting from dungeon $i$, he can choose $1$ of them and move between dungeons; there is no other way to move between dungeons. Also, even when he visits dungeon $i$ again, he cannot choose a road and move until he clears it again.

Now, Nafmo starts clearing dungeon $1$. He wants to pass through some dungeons and finish the game upon clearing dungeon $N$. Find the maximum possible value of Nafmo's satisfaction. If the satisfaction can be made arbitrarily large, print inf.

Here,

• Nafmo's satisfaction: the value obtained by subtracting "the total time spent traveling between dungeons" from "the total time spent clearing dungeons"
• He may clear the same dungeon and pass through the same road any number of times
• The time needed to switch from clearing a dungeon to traveling is negligible

Input

$N\ M$
$A_1 \ \dots \ A_N$
$a_1 \ b_1 \ c_1$
$\vdots$
$a_M \ b_M \ c_M$

• $2 \leq N \leq 2500$
• $1 \leq M \leq min(N\times(N-1),5000)$
• $1 \leq A_i \leq 10^9 \ (1 \leq i \leq N)$
• $1 \leq a_j,b_j \leq N \ (1 \leq j \leq M)$
• $a_j \neq b_j \ (1 \leq j \leq M)$
• $a_j \neq a_k$ or $b_j \neq b_k \ (1 \leq j < k \leq M)$
• $1 \leq c_j \leq 10^9 (1 \leq j \leq M)$ Added at 14:14: The upper bound of this constraint was corrected from $N$ to $10^9$.
• There exists a path from dungeon $1$ to dungeon $N$
• All input values are integers

Output

Print Nafmo's satisfaction.

Sample

3 2
2 2 2
1 2 1
2 3 1

4

3 3
2 2 2
1 2 1
2 3 1
2 1 1

inf

4 3
594 437 766 437
2 3 63
2 4 10
1 2 61

1397