Автопробег
Маршрут Антилопы-Гну пролегает по гостеприимным и хлебосольным местам. При этом существует некоторая вероятность, что в любой город на их маршруте поступит одна очень важная телеграмма, или вдруг Паниковский опять возьмется за старое, и тогда в этом городе придется подзадержаться на 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} в любую сторону, длительность любого маршрута не изменится.
Выходные данные
В первую строку выходного файла необходимо вывести одно целое число — количество городов, через которые пролегает оптимальный маршрут. Во второй строке должны быть перечислены через пробел номера этих городов в порядке следования.