Big Macs Around the World

Bessie is studying her favorite subject, macroeconomics, at cowllege. For her final project she will present research on exchange rates between countries around the world.

To make her presentation more lively, she wants to show the relative prices of Big Macs around the world. Suppose she wants the smallest value of a Big Mac in a target country, given its value in a starting country and a list of exchange rates that convert one country's currency into another's. For example:

• A Big Mac is worth 60 USD in the United States.
• The exchange rate from USD to CAD is 0.2 CAD per USD.
• The exchange rate from USD to GBP is 5.00 GBP per USD.
• The exchange rate from GBP to CAD is 0.5 CAD per GBP.
• The exchange rate from CAD to USD is 5.00 USD per CAD.

Bessie wants the smallest possible value of the Big Mac in Canada reachable through a sequence of currency conversions. There are two routes:

• USD directly to CAD: 60.00 USD × 0.2 CAD/USD = 12.00 CAD.
• USD to GBP to CAD: 60.00 USD × 5.00 GBP/USD × 0.5 CAD/GBP = 150.00 CAD.

Bessie prefers the first route, paying 12.00 CAD instead of 150.00 CAD.

Bessie has $N$ ($1 \le N \le 2000$) countries labeled $1$ to $N$, together with a list of $M$ ($1 \le M \le 25000$) exchange rates $e_{ij}$ ($0.1 < e_{ij} \le 10$), each directed from country $i$ to country $j$ ($1 \le i \le N$; $1 \le j \le N$). Converting from country $i$ to country $j$ multiplies the current value by $e_{ij}$.

Given the value $V$ ($1 \le V \le 10^{12}$, not necessarily an integer) of the Big Mac in the starting country $A$ ($1 \le A \le N$), find the smallest possible value of the Big Mac in country $B$ ($1 \le B \le N$; $B \ne A$) after a sequence of conversions. If no minimum exists (the value can be made arbitrarily small), output 0.

It is guaranteed that the answer, if not 0, lies between 1 and $10^{15}$. It is also guaranteed that from any country's currency it is possible to reach any other country's currency.

• Line 1: Five space-separated numbers: $N$, $M$, $V$, $A$, $B$.
• Lines 2 to $M+1$: Three space-separated numbers describing one exchange rate: $i$, $j$, $e_{ij}$.

• Output the smallest possible value of the Big Mac in country $B$, rounded to exactly two decimal places (round half up). If no minimum exists, output a single 0.