Eduardo is planning for a trip to Mexico this summer and he needs to buy some pesos for his trip. Eduardo doesn't trust currency exchange businesses as he believes they give bad rates, so instead he will ask his friends to trade currencies.

Eduardo has $M$ friends that are willing to trade currencies. Each friend is willing to trade some currency that they have for some other currency that they want. Also, each friend has their own exchange rate and is willing to trade any amount of currency (even fractional amounts).

Eduardo currently has $D$ Canadian dollars and wants to get as many pesos as possible so that he can fully enjoy his trip. Can you help Eduardo figure out how many pesos he can get?

Input Specification

The standard input contains 10 datasets. Each dataset begins with three integers $N$, $M$, $D$ $(2\le N\le 5000,1\le M,D\le 5000)$: the number of available currencies, the number of friends willing to trade currency, and how many dollars Eduardo currently has, respectively. The Canadian dollar has index $1$, and the peso has index $N$.

The next $M$ lines each describe the trades that Eduardo's friends are willing to perform. Each line contains three integers $A$, $B$, $(1\le A,B\le N)$ and one positive real number $R$ $(0.1\le R\le 10)$ given to four decimal places, where:

• $A$ is the index of the currency that the friend wants.
• $B$ is the index of the currency that the friend has.
• $R$ is the exchange rate that the friend set. The friend will sell $1$ unit of currency $B$ for $R$ units of currency $A$.

For the first four cases, each exchange rate $R$ is greater than or equal to $1$.

Output Specification

For each dataset, output the maximum number of pesos that Eduardo can get, rounded to two decimal places. If Eduardo can get more than one billion pesos, output Billionaire! instead. It is guaranteed that the answer will not be within 1000 pesos of one billion.

Sample Input (Two Datasets Shown)

3 3 3
1 3 1.0000
1 2 2.0000
2 3 0.3000
4 4 1
1 2 0.5000
2 3 0.5000
3 4 0.5000
4 1 7.0000

Sample Output

5.00
Billionaire!

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org