Big Mac Exchange Rates

Bessie is studying Macroeconomics and is interested in the relative prices of Big Macs around the world. She considers N countries labeled from 1 to N and M directed exchange rates between them. Given the Big Mac price V in her starting country A and a destination country B (with A ≠ B), she wants to find the smallest possible value in country B by a series of currency exchanges.

If an exchange rate from country i to country j is given as e_ij, then after converting the price, the Big Mac value becomes:

[ V \times \prod_{(i \to j) \in \text{path}} e_{ij} ]

Sometimes, by exchanging currencies along cycles, the price can be made arbitrarily low. In other words, if there exists a cycle whose product is less than 1 (i.e.\ \(\prod_{cycle} e_{ij} < 1\); equivalently, \(\sum_{cycle} \ln(e_{ij}) < 0\)), then the minimal attainable value does not exist and you should output 0.

The input guarantees that for any country, it is possible to reach any other country.

inputFormat

The first line contains five values: N M A B V, where

• N (1 ≤ N ≤ 2000) is the number of countries.
• M (1 ≤ M ≤ 25000) is the number of exchange rates.
• A (1 ≤ A ≤ N) is the starting country.
• B (1 ≤ B ≤ N, B ≠ A) is the destination country.
• V (1 ≤ V ≤ 10¹²) is the value of the Big Mac in country A (it may not be an integer).

The next M lines each contain three values: i j e indicating that the exchange rate from country i to j is e (with 0.1 < e ≤ 10).

outputFormat

Output a single number: the smallest possible value of a Big Mac in country B after a series of currency conversions. If the price can be made arbitrarily small due to a cycle with product less than 1, output 0.

sample

3 4 1 2 60.00
1 2 0.2
1 3 5.0
3 2 0.5
2 1 5.0

12.000000