Маршрут Антилопи-Гну прозодить по гостинним та хлібосольним місцям. При цьому існує деяка ймовірність, що у довільне місто їхньому маршруті поступить одна дуже важлива телеграма, або раптом Панвковський знову візьметься за старе, і тоді у цьому місті доведеться підзатриматись на \textbf{24} години. Звичайно, час проходження одного й того ж маршруту --- величина непостійна і залежить від удачі. У славне ж місто Черноморськ діти лейтенанта Шмідта повинні приїхати якомога швидше, ну не зі стовідсотковою ймовірністю, а з ймовірністю, не меншою заданої. При цьому ймовірності затриматись у довільному місті на їхньому маршруті однакові і самі ці затримки ніяк не залежать одна від одної. Назвемо тривалістю маршруту таке число \textbf{T}, що ймовірність проходження маршруту за час, який не перевищує \textbf{T}, буде не меншим заданої ймовірності \textbf{P}. Під час проходження маршруту включається можлива затримка у першому і останньому місті. Допоможіть їм знайти маршрут мінімальної тривалості. \InputFile У першому рядку два цілих числа \textbf{N} і \textbf{M} --- кількість міст і кількість доріг між ними та два дійсних числа \textbf{P} --- задана ймовірність, з якою шукається час проходження маршруту і \textbf{P_1} --- ймовірність затримки на \textbf{24} години у кожному місті (\textbf{2} ≤ \textbf{N} ≤ \textbf{1000}, \textbf{1} ≤ \textbf{M} ≤ \textbf{10000}, \textbf{0} ≤ \textbf{P}, \textbf{P_1} ≤ \textbf{1}). \textbf{P} і \textbf{P_1} задано з п'ятьма знаками після десяткової крапки. Далі йде \textbf{M} рядків --- описи доріг, у кожному три цілих числа \textbf{A_i}, \textbf{B_i}, \textbf{L_i} --- номери міст, з'єднані заданою дорогою та час її проходження в годинах (\textbf{1} ≤ \textbf{L_i} ≤ \textbf{1000}). Міста пронумеровано числами від \textbf{1} до \textbf{N}. Маршрут прокладується від міста з номером \textbf{1} у місто з номером \textbf{N}. Кожна пара міст з'єднана не бвльше ніж однією дорогою. Жодна дорога не з'єднує місто саме з собою. По дорогам можна їздити в обидві сторони. Гарантується, що між довільними двома містами існує шлях, і що при зміні \textbf{P} на не більше ніж на \textbf{10^\{--9\}} у довільну сторону, тривалість довільного маршруту не зміниться. \OutputFile У перший рядок вихідного файлу необхідно вивести одне ціле число --- кількість міст, через які пролягає оптимальний маршрут. У другому рядку повинні бути перераховані через пропуск номери цих міст у порядку слідування.