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