题目描述

$\red{Bessie}$正在牛学院$\red{(cowllege)}$学习她最爱的课程：宏观经济学。为了准备她的毕业课题， 她要发表一篇关于国家之间汇率的研究报告。

为了使得她的报告更加生动，她将展示世界各地的巨无霸的价格$\red{(}$虽然她极其 讨厌这些不降的垃圾食品$\red{)}$。

通过给出巨无霸在某个国家的价格和一些国家 货币之间的汇率，$\red{Bessie}$想知道一个巨无霸在某个国家的最便宜的价格。

下面看个例子： 一个巨无霸在美国售价$\red{60}$美刀。 美刀对加拿大元的的汇率是$\red{0.2，}$也就是$\red{1}$美刀可以兑换$\red{0.2}$加拿大元，美刀对英镑的汇率是$\red{5.00，}$也就是$\red{1}$美刀可以兑换$\red{5.00}$英镑，英镑对加拿大元的汇率是$\red{0.5，}$也就是$\red{1}$英镑可以兑换$\red{0.5}$加拿大元，加拿大元对美刀的汇率是$\red{5.00，}$也就是$\red{1}$加拿大元可以兑换$\red{5.00}$ 美刀。

$\red{Bessie}$想要找到在加拿大购买一个巨无霸最便宜的方式（通过货币的流通与兑换）。 以下有两种方式： 从美元直接兑换加拿大元，这样一个巨无霸价值 $\red{60 }$美刀 $\red{\times 0.2 }$加拿大元 $\red{/ 1 }$美刀 $\red{= 12 }$加拿大元。 从美元兑换成英镑，再有英镑兑换为加拿大元，这样一个巨无霸价值 $\red{60 }$美刀$\red{\times 5 }$英镑 $\red{/ 1 }$美元 $\red{\times 0.5}$加元 $\red{/ 1 }$英镑 $\red{= 150 }$加元。

$\red{Bessie}$会选择前一种兑换方式，这样她购买一个巨无霸可以只付$\red{12}$加元。

$\red{Bessie}$在研究$\red{N (1 <= N <= 2,000) }$个国家，编号为$\red{1...N}$。她列出了$\red{M(1 <= M<= 25,000) }$种兑换方式和相对应的汇率 $\red{e_{ij} (0.1 < e_{ij} <= 10)，}$表示国家$\red{i}$和$\red{j}$的货币 的兑换比例是$\red{e_{ij}(}$是单向的$\red{)}$。

给出一个实数$\red{V (1 <= V <= 1,000,000,000,000)，}$表示一个巨无霸在$\red{A}$国$\red{(1 <= A <= N)}$的售价。

你能够帮助她找到一种方式使得一个巨无霸在$\red{B}$国$\red{(1 <= B <= N}$; $\red{B != A)}$的售价旧能少吗？

如果售价没有最小值，输出$\red{0}$。 保证最终答案如果不是$\red{0，}$一定在$\red{1}$到$\red{10^{15}}$之间。 保证任何国家的货币可以兑换为任何另一个国家的货币。

输入格式

第$\red{1}$行： $\red{5}$个空格分隔的数字： $\red{N, M, V, A, B }$

第$\red{2...M+1}$行： 三个空格分开的数字： $\red{i, j, e_{ij}}$

输出格式

第$\red{1}$行：如果不存在最小值，为$\red{0}$。否则是一个正数，和标准答案的差的绝对值不能大于$\red{10^{-6}}$。

样例

输入样例

3 4 60 1 2
1 2 0.2
1 3 5
3 2 0.5
2 1 5

输出样例

12.00