12. Дорожный вопрос

Дорожный вопрос стоит уже много-много лет очень остро в Байтруссии. А одна из главных проблем $-$ коррупция среди дорожных работников. Они построили огромные въездные ворота во всех городах страны и собирают налоги за посещение городов. Из-за нарастающей социальной напряжённости руководство дорожной службы решило ввести некоторые ограничения для своих служащих. Первое из таких ограничений, которое будет опробовано $-$ запрет требовать налог с путника, который до въезда в город $X$ уже заплатил налог в одном из городов $Y$, куда можно добраться из $X$ напрямую или через какие-то другие города, возможно, не посещённые путником. При этом, и этому дорожные работники будут очень рады, путешественник всё равно может заплатить налог в городе $X$, если посчитает для себя это выгодным.

Чиновнику Василию Петровичу нужно добраться из столицы Байтруссии города М. в малую столицу $-$ город С., на финал международного чемпионата по программированию. При этом он, конечно, хочет потратить как можно меньше денег на оплату налогов (в это сложно поверить, но даже чиновники вынуждены платить эти налоги). Зная, что все дороги в стране односторонние, и располагая сведениями о въездных налогах во всех городах, помогите чиновнику проложить оптимальный маршрут из города М. в город С.

В первой строке ввода записано два целых числа $n$ и $m$ ($2 \le n \le 100\,000$, $1 \le m \le 500\,000$) $-$ количество городов и дорог в Байтруссии. Во второй строке содержится $n$ целых чисел $C_i$ ($0 \le C_i \le 10\,000$) $-$ величины налогов за въезд в города. Далее в $m$ строках записано по два целых числа $x_i$ и $y_i$ ($1 \le x_i, y_i \le n$, $x_i \ne y_i$), описывающих $i$-ю дорогу, идущую из города $x_i$ в город $y_i$. Между парой городов может быть несколько дорог. Для удобства город М. имеет номер 1, а город С. $-$ номер $n$. Гарантируется, что из города М. можно добраться в город С. Числа в строках разделяются одиночными пробелами.

Выведите единственное число $-$ минимальную сумму налогов, которую нужно заплатить на пути из М. в С.