В стране $n$ городов, некоторые из которых соединены между собой дорогами. Для того, чтобы проехать по одной дороге требуется один бак бензина. В каждом городе бак бензина имеет разную стоимость. Вам требуется добраться из первого города в $n$-ый, потратив как можно меньшее количество денег. \InputFile Сначала идет количество городов $n~(1 \le n \le 100)$, затем идет $n$ чисел, $i$-ое из которых задает стоимость бензина в $i$-ом городе (все числа целые из диапазона от $0$ до $100$). Затем идет количество дорог $m$ в стране, далее идет описание самих дорог. Каждая дорога задается двумя числами --- номерами городов, которые она соединяет. Все дороги двухсторонние (то есть по ним можно ездить как в одну, так и в другую сторону); между двумя городами всегда существует не более одной дороги; не существует дорог, ведущих из города в себя. \OutputFile Выведите одно число --- суммарную стоимость маршрута или $-1$, если добраться невозможно. \includegraphics{https://static.e-olymp.com/content/34/341ba1cdbde7f2947335938bd85415067f5437f2.gif}