AT_wupc2019_f RPG

[problemUrl]: https://atcoder.jp/contests/wupc2019/tasks/wupc2019_f カトーくんは、とある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` を出力してください。

入力は以下の形式で標準入力から与えられる。 ``` \(N\) \(M\) \(c_2\) \(c_3\) \(\dots\) \(c_{N-1}\) \(a_1\) \(b_1\) \(a_2\) \(b_2\) \(\vdots\) \(a_M\) \(b_M\) ```

条件を満たすような「回復所」の設置コストの合計の最小値を出力してください。 条件を満たすことができない場合は、 `-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\\) へ向かうパスが存在する。また、閉路は存在しない。 - 入力される値はすべて整数である。 ### Sample Explanation 1 場面 \\\\(3\\\\) と場面 \\\\(5\\\\) を選ぶのが最適です。 ### Sample Explanation 2 場面 \\\\(2\\\\) から場面 \\\\(3\\\\) の間に「休憩所」を設置することができません。