Problem
この国には N 個の都市があり、そのうちのいくつかは道路で結ばれています。 1 本の道路を走行するのに 1 タンクのガソリンが必要です。各都市では、ガソリン タンクのコストが異なります。できるだけ少ないお金で、最初の都市から N 番目の都市に移動する必要があります。将来の使用のためにガソリンを購入することはできません。
入力
最初の行には数値 N (1≤N≤100) が含まれ、次の行には N の数値が含まれ、その i 番目は i 番目の都市のガソリン代を指定します (これらは 0 から 100 までの整数です) ）。次に M という数字が続きます –国内の道路の数、その後に道路自体の説明が続きます。各道路は 2 つの番号で指定されます –接続する都市の数。すべての道路は双方向です (つまり、一方向と反対方向の両方に運転できます)。2 つの都市の間には常に 1 本の道路しかなく、都市からその都市に通じる道路はありません。
出力
単一の数値を出力するために必要 –ルートの総コスト、またはそこに到達できない場合は -1。
例
<頭>
| # |
入力 |
出力 |
<本体>
| 1 |
5
3 6 1 7 6
8
1 2
5 4
5 1
3 4
5 2
2 4
2 3
3 1
|
3 |