Yanacaqdoldurma məntəqələri

Ölkədə $n$ şəhər mövcuddur və bəziləri yollarla bir-birinə bağlıdır. Hər bir yolu keçmək üçün bir benzin çəni tələb olunur. Hər şəhərdə benzin çəninin qiyməti fərqlidir. Məqsədiniz birinci şəhərdən $n$-ci şəhərə mümkün olan ən az xərclə çatmaqdır.

Giriş verilənləri

Əvvəlcə şəhərlərin sayı $n(1\le n\le 100)$ verilir. Sonra $n$ ədəd təqdim olunur, burada $i$-ci ədəd $i$-ci şəhərdə benzinin qiymətini göstərir (bütün ədədlər $0$-dan $100$-ə qədər tam ədədlərdir). Daha sonra ölkədəki yolların sayı $m$ verilir və ardınca yolların təsviri təqdim olunur. Hər yol iki ədəd ilə təsvir edilir — birləşdirdiyi şəhərlərin nömrələri. Bütün yollar ikitərəflidir (yəni hər iki istiqamətdə hərəkət etmək mümkündür); iki şəhər arasında bir yoldan çox olmur; özünə aparan yollar mövcud deyil.

Çıxış verilənləri

Marşrutun ümumi dəyərini və ya çatmağın mümkün olmadığını göstərən $-1$ ədədini çıxarın.

Nümunələr