問題文

カトーくんは、とあるRPGのシナリオを作っています。 このRPGでは \(N\) 個の場面があり、各場面は既に「戦闘」か「空き地」のどちらかであると決まっています。 また、 \(M\) 個の場面間をつなぐ移動通路があり、\(i\) 番目の通路は、場面 \(a_i\) から 場面 \(b_i\) へ移動が可能です。 最初、RPGの主人公であるシンヤくんは、場面 \(1\) にいて、自由に通路を移動し、場面 \(N\) に到達したらゲームクリアです。

シンヤくんには「元気」と「疲労」の2種類の状態があります。 「元気」状態では戦闘に挑むことができますが、「疲労」状態では戦闘することができません。 「疲労」状態で「戦闘」場面に到達するとゲームオーバーとなります。

シンヤくんは「元気」状態でゲームを開始します。 「戦闘」場面を通過すると、疲れて「疲労」状態になります。 「疲労」状態から「元気」状態に戻るためには「回復所」を通過する必要があります。

「回復所」は任意の「空き地」場面に設置することができます。 場面 \(i \ (2 \leq i \leq N-1)\) に回復所を設置するコストは \(c_i\) です。

現在、「回復所」をどこに設置するかは決まっていません。 そこでカトーくんは、以下の条件を満たすように、「回復所」を設置することにしました。

• 場面 \(1\) から動き始めたシンヤくんが場面 \(N\)に向かうどのような移動を選んでも、任意の「戦闘」場面から他の「戦闘」場面に達する間に、少なくとも1回は「回復所」を通過する。
• ゲームクリア時のシンヤくんの状態は「疲労」でも「元気」でもよい。

以上の条件を満たすようにカトーくんが「回復所」を設置する際に必要なコストの合計の最小値を求めてください。 どのように「回復所」を設置しても条件を満たすことができなければ、 -1 を出力してください。

制約

• \(3 \leq N \leq 500\)
• \(N-1 \leq M \leq 1000\)
• \(-1 \leq c_i \leq 10^9 \ (2 \leq i \leq N-1)\)
  • \(c_i = -1\) ならば、場面 \(i\) は「戦闘」場面である。
  • \(c_i \geq 0\)ならば、場面 \(i\) は「空き地」場面であり、そこに「休憩所」を設置するコストは \(c_i\) である。
• \(1 \leq a_i , b_i \leq N \ (1 \leq i \leq M)\)
  • 場面 \(a_i\) から、場面 \(b_i\) への移動通路があることを示す。
• \(N\) 頂点 \(M\) 辺の有向グラフとみたとき、全ての頂点に対し、頂点 \(1\) からのパスと、頂点 \(N\) へ向かうパスが存在する。また、閉路は存在しない。
• 入力される値はすべて整数である。

入力例 1

7 7
-1 100 10 1 -1
1 2
2 3
3 6
2 4
4 5
5 6
6 7

出力例 1

101

場面 \(3\) と場面 \(5\) を選ぶのが最適です。

入力例 2

4 3
-1 -1
1 2
2 3
3 4

出力例 2

-1

場面 \(2\) から場面 \(3\) の間に「休憩所」を設置することができません。