Домашнее задание задача

Задача C: Заправки-2
В стране n городов, некоторые из которых соединены между собой дорогами. Для того, чтобы проехать по одной дороге, требуется один бак бензина. Помимо этого у вас есть канистра для бензина, куда входит столько же топлива, сколько входит в бензобак. В каждом городе бак бензина имеет разную стоимость. Вам требуется добраться из первого города в n-й, потратив как можно меньшее денег. В каждом городе можно заправить бак, заправить бак и канистру или же перелить бензин из канистры в бак. Это позволяет экономить деньги, покупая бензин в тех городах, где он стоит дешевле, но канистры хватает только на одну заправку бака!

Формат входных данных
В первой строке вводится число n (1<=n<=100), в следующей строке идет n чисел, i-е из которых задает стоимость бензина в i-м городе (всё это целые числа из диапазона от 0 до 100). Затем идет число M – количество дорог в стране, далее идет описание самих дорог. Каждая дорога задается двумя числами – номерами городов, которые она соединяет. Все дороги двухсторонние (то есть по ним можно ездить как в одну, так и в другую сторону), между двумя городами всегда существует не более одной дороги, не существует дорог, ведущих из города в себя.

Формат выходных данных
Требуется вывести одно число – суммарную стоимость маршрута или -1, если добраться невозможно.

Входные данные
4
1 10 2 15
4
1 2
1 3
4 2
4 3
Выходные данные
2