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