Дорожная сеть Байтруссии пришла в упадок: по каждой дороге можно проехать только в одном направлении, одни и те же два города могут соединять несколько дорог, а между другими двумя городами вообще может не быть пути по дорогам...
Чтобы спасти положение, парламент Байтруссии издал закон, согласно которому за въезд в каждый город путешественник обязан заплатить налог. Величина налога фиксирована для каждого города и определяется бургомистром.
Закон вызвал недовольство торговых гильдий, которые обратились к королю с петицией. В результате король своим указом запретил требовать налог за въезд в город X с путешественника, который уже заплатил налог в некотором городе Y, в который можно добраться из X напрямую или через некоторые другие города (не обязательно те, через которые тот уже прошёл). Тем не менее, в этой ситуации путешественник может по собственной инициативе заплатить налог в городе X, если сочтёт это для себя выгодным. Платить налог можно только в момент въезда в город.
Купцу первой гильдии Биту Битычу Байтоградскому нужно добраться из столицы Байтруссии М. в крупный портовый город С. При этом купец, естественно, хочет заплатить как можно меньшую сумму в качестве налогов. Обратите внимание, что Бит уже находится в городе М., а значит, не обязан - и не может - заплатить в нём налог до начала движения.
По информации о карте дорог Байтруссии и величине въездного налога для каждого города проложите оптимальный маршрут для купца. Гарантируется, что путь из М. в С. по дорогам Байтруссии существует.
В первой строке ввода записано два целых числа n и m (2 ≤ n ≤ 100000, 1 ≤ m ≤ 500000) - количество городов и дорог в Байтруссии. Во второй строке содержится n целых чисел C_i (0 ≤ C_i ≤ 10000) - величины налогов за въезд в города. Далее в m строках записано по два целых числа x_i и y_i (1 ≤ x_i, y_i ≤ n, x_i ≠ y_i), описывающих i-ю дорогу, идущую из города x_i в город y_i. Между парой городов может быть несколько дорог. Для удобства город М. имеет номер 1, а город С. - номер n. Гарантируется, что из города М. можно добраться в город С. Числа в строках разделяются одиночными пробелами.
Выведите единственное число - минимальную сумму налогов, которую нужно заплатить на пути из М. в С.