Problem I
Red vs Blue

Image owned by Rooster Teeth, commons.wikimedia.org

Your company is organising a computer security exercise and you are on the attacking team, that is to say the red team. Your team has managed to get their hands on a schematic of the intranet the blue team is using. Another team member also managed to access one of the computers on this intranet and set it up such that you could SSH directly into it.

Now it is up to you to use this to connect to a particular computer on the intranet where the password you need is stored. To connect to it you need to SSH between the computers on the intranet that are connected. For each such connection there is however some chance that the system notices the unusual traffic and closes your SSH session. When this happens you need to connect to the first computer again and start over.

To avoid having to start from scratch every time you can change the SSH settings of computers you have SSH-ed into such that you can SSH into them directly the next time around if your SSH session is closed. This takes $B$ units of time. SSH-ing from one computer to another on the intranet takes $S$ time units and SSH-ing into a computer from the outside takes $R$ time units.

As the algorithmic expert on the team it is now up to you to find a way to get a hold of the password in the least amount of time. This is of course up to random chance so we want the strategy that will take the least expected time.

Input

The first line of input contains two integers $1 \leq N, M \leq 5\, 000$, separated by a space. $N$ gives the number of computers on the intranet and $M$ the number of connections between them.

Next there is a line with three integers $1 \leq B, S, R \leq 10^4$, the constants in the description above.

Next there are $M$ lines, each with three values $1 \leq x, y \leq N$ and $0 \leq p \leq 1$. Such a line denotes that it is possible to SSH from computer number $x$ to computer number $y$ on the intranet with probability $p$, and then there is a $1 - p$ chance that the SSH session is closed. It will always hold that $x, $ are different integers and $p$ a floating point number with at most $6$ digits after the decimal point.

Computer number $1$ on the intranet is the one you can connect to initially and computer number $N$ on the intranet is the one containing the password you want.

Output

Print the expected time to connect to computer number $N$ if the best possible strategy is used. You may assume that this is always possible and that the expected time is finite. The answer is considered correct if its relative or absolute error is at most $10^{-5}$.

Explanation of samples

In the first sample there is only one connection, and there is a fifty-fifty chance using it will get you detected. If you do not get detected it takes only $100$ units of time. But if you get detected, then it takes $1000$ units of time to reconnect and then another $100$ to try again. Thus each failed attempt costs an extra $1100$ units of time. On average you will fail once if you try until you succeed, so the answer is $1200$.

In the second sample there are two ways to our target, and the better one is the way through computers $3$ and $4$. We connect to computer $3$, which fails an average of $0.25$ times, so it takes $150$ units of time. Then we change the SSH settings on computer $3$ which takes $1000$ units of time. Next we try to get from computer $3$ to $4$ which fails an average of $9$ times. But we can connect to computer $3$ directly if we fail, so each failed attempts takes only $200$ units of time. Thus this takes us $1900$ units of time on average. To get to our target we do not change the settings on computer $4$, we simply try to move to the target computer. This fails an average of $0.25$ times, but if we fail, then we have to try to get to computer $4$ again. That takes $1900$ units of time on average, in addition to $100$ units to reconnect to the system and $100$ units to try to move from $4$ to $5$ again. Thus it takes us $100 + 0.25 \cdot 2100 = 625$ units of time on average to move from $4$ to $5$. In total this gives $3675$ units of time.

2 1
10 100 1000
1 2 0.5

1200

5 5
1000 100 100
1 2 0.8
2 5 0.01
1 3 0.8
3 4 0.1
4 5 0.8

3675