У країні міст, деякі з яких з'єднані між собою дорогами. Для того, щоб проїхати по одній дорозі потрібно один бак бензину. У кожному місті бак бензину має різну віртість. Вам потрібно дістатись з першого міста у -те, витративши якомога меншу кількість грошей.
Спочатку йде кількість міст , потім йде чисел, -те з яких задає вартість бензину в -ому місті (всі числа цілі з діапазону від до ). Потім йде кількість доріг в країні, далі йде опис самих доріг. Кожна дорога задається двома числами — номерами міст, які вона з'єднує. Всі дороги двосторонні (тобто по ним можна їздити як в одну, так і в іншу сторону); між двома містами завжди існує не більше однієї дороги; не існує доріг, які ведуть з міста в себе.
Виведіть одно число — сумарну вартість маршруту або , якщо дістатись неможливо.