Задача Заправки

Описание

В стране N городов, некоторые из которых соединены между собой дорогами. Для того, чтобы проехать по одной дороге требуется один бак бензина. В каждом городе бак бензина имеет разную стоимость. Вам требуется добраться из первого города в N-ый, потратив как можно меньшее количество денег.

Формат входных данных

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

Формат выходных данных

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