問題文

Nafmoくんは，$N$ 個 のダンジョンからなるゲームをこれから始めようとしています．
ダンジョンにはそれぞれ $1$ から $N$の番号が振られており，ダンジョン $i (1 \leq i \leq N)$ は攻略に $A_i$ 時間かかります．
また，ダンジョン間を結ぶ一方通行の道が $M$ 本 あり，それぞれ $1$ から $M$ の番号が振られています．道 $j (1 \leq j \leq M)$ は ダンジョン$a_j$ から ダンジョン$b_j$ を結ぶ一方通行の道であり，移動には $c_j$ 時間かかります．
ダンジョン$i$ を攻略したとき，ダンジョン $i$ を始点とする道が存在する場合，$1$ つ選んでダンジョン間を移動することができ，それ以外にダンジョンを移動する手段は存在しません．また，再度ダンジョン $i$ を訪れた場合でも，再攻略するまで道を選んで移動することはできません．

今，Nafmoくんは ダンジョン $1$ の攻略を始めます．いくつかのダンジョンを経由し，ダンジョン$N$ の攻略とともにゲームを終了したいと思っています．Nafmoくんの満足度は最大でいくつになるかを求めてください．満足度をいくらでも大きくできる場合は inf と出力してください．

ただし，

• Nafmoくんの満足度：「ダンジョンを攻略するのにかかった時間の総和」 から 「ダンジョン間の移動時間の総和」 を引いたもの
• 同じダンジョン，同じ道を何度も攻略したり通ったりしても良い
• ダンジョン攻略から移動の切り替えにかかる時間は無視できるものとする

入力

$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$ または $b_j \neq b_k \ (1 \leq j < k \leq M)$
• $1 \leq c_j \leq 10^9 (1 \leq j \leq M)$ 14:14追記：制約の上限を $N$ から $10^9$ へ修正しました．
• ダンジョン $1$ から ダンジョン $N$ に到達できる経路が存在する
• 入力はすべて整数

出力

Nafmoくんの満足度を出力してください

サンプル

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