Minimum Transfer Amount

There are \(n\) people. Some of them can transfer money between each other’s bank accounts with a fee deducted from the transferred amount. The fee for each transfer is given as a percentage. Specifically, if an amount \(x\) is transferred along an edge with fee \(f\), the receiver gets \(x\times\left(1-\frac{f}{100}\right)\). Given a network of transfers and the fee for each allowed transfer, determine the minimum amount of money that person A needs to send so that after a sequence of transfers, person B receives exactly 100 units.

In other words, if the chosen path from A to B has fees \(f_1, f_2, \dots, f_k\), then person B will receive:

[ 100_{received} = x \times \prod_{i=1}^{k}\left(1-\frac{f_i}{100}\right). ]

You are to compute the minimum \(x\) such that \(x \times \prod_{i=1}^{k}\left(1-\frac{f_i}{100}\right) \geq 100\). Equivalently, find the path maximizing \(\prod_{i=1}^{k}\left(1-\frac{f_i}{100}\right)\), and output \(\frac{100}{\text{max product}}\). It is guaranteed that there is at least one path from A to B.

inputFormat

The first line contains two integers \(n\) and \(m\), representing the number of people and the number of allowed transfers.

Each of the next \(m\) lines contains three values: \(u\), \(v\) and \(f\), where person \(u\) can transfer money to person \(v\) with a fee of \(f\) percent.

The last line contains two integers \(A\) and \(B\) representing the starting person (sender) and the target person (receiver), respectively.

outputFormat

Output a single number, which is the minimum amount of money person A needs to send, such that person B receives at least 100 units. The answer should be printed with precision up to 6 decimal places.

sample

4 4
1 2 10
2 3 20
3 4 30
1 4 50
1 4

198.412698