Rally
The route of Antelope Gnu lies through hospitable and generous places. There is a certain chance that an important telegram arrives to any of the towns on their route, or that Panikovskiy lapses into his old ways, meaning the crew will have to spend an extra day in that town. Naturally, the time necessary to cover the same part of the route is never the same and depends on pure luck. However, the team must arrive to the glorious town of Chernomorsk as soon as possible, well, perhaps not 100% on time, but with a pre-defined probability of it. At the same time the chance of delays in any of the towns on their route is the same, and the delays don’t depend on each other. Let the route duration be T, such that the chance of covering the route in time not exceeding T, is not smaller than the given probability P. The time of covering the route includes possible delays in the first and last towns lying on the route.
Help the team find the route with the smallest duration.
Input
The first line of the input file contains two integers N and M — the number of towns and the number of roads between them, and two real numbers P — the predefined probability used to determine the route duration and P_1 — the probability of 24 hour delay in every town (2 ≤ N ≤ 1000, 1 ≤ M ≤ 10000, 0 ≤ P, P_1 ≤ 1). P and P_1 are given with five digits after the decimal point.
The following M lines contain the descriptions of roads with three integers A_i, B_i, L_i each: the numbers of towns linked by a given road and time necessary to cover that distance in hours (1 ≤ L_i ≤ 1000). The roads are bidirectional. Towns are numbered from 1 through N. The route is set from the town with the number 1 to the town with the number N. No pair of towns is connected with more than one road. No road connects a town to itself. It is guaranteed that there is a path between any pair of towns and that the duration of any route doesn't change if P is changed by not more than 10^{–9} in any direction.
Output
The first line of the output file must contain a single integer ＿ the number of towns on the optimal route. The second line must contain the numbers of these towns in the order of passing, separated by spaces.