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