Дорожнє питання
Дорожня мережа Байтрусії занепала: кожна дорога є односторонньою, між двома містами може бути кілька доріг, а деякі міста можуть взагалі не мати з'єднань...
Щоб виправити ситуацію, парламент Байтрусії ухвалив закон, згідно з яким мандрівник повинен сплатити податок за в'їзд у кожне місто. Розмір податку фіксований для кожного міста і встановлюється його бургомістром.
Цей закон викликав невдоволення серед торгових гільдій, які звернулися до короля з петицією. У відповідь король видав указ, що забороняє стягувати податок за в'їзд у місто 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. Гарантується, що з міста М можна дістатися в місто С. Числа в рядках розділяються одиничними пробілами.
Вихідні дані
Виведіть єдине число - мінімальну суму податків, яку потрібно сплатити на шляху з М у С.