Problem
N شهر در کشور وجود دارد که برخی از آنها از طریق جاده به یکدیگر متصل هستند. رانندگی در یک جاده به یک باک بنزین نیاز دارد. در هر شهر یک باک بنزین هزینه متفاوتی دارد. شما باید از اولین شهر به شهر نهم بروید و تا حد امکان کمتر پول خرج کنید. شما نمی توانید بنزین برای استفاده در آینده بخرید.
ورودی
خط اول شامل عدد N (1≤N≤100) است، سطر بعدی حاوی N عدد است که i-ام آن هزینه بنزین در شهر i را مشخص می کند (این اعداد صحیح از 0 تا 100 هستند. ). سپس عدد M – تعداد جاده های کشور و به دنبال آن شرحی از خود جاده ها. هر جاده با دو عدد داده می شود – تعداد شهرهایی که به آن متصل است. همه راه ها دو طرفه هستند (یعنی می توان آنها را هم در یک جهت و هم در جهت دیگر راند)، همیشه بین دو شهر یک جاده بیشتر نیست، هیچ جاده ای از شهر به سمت خودش منتهی نمی شود. div>
خروجی
برای خروجی یک عدد مورد نیاز است – هزینه کل مسیر یا -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 |