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