略微翻译了一下

埃西正在学习她最喜欢的科目,宏观经济学。最后的项目,她将呈现研究世界各国货币之间的汇率。

为了使演讲更生动,她想计算世界各地的巨无霸的相对价格,尽管他们令人讨厌的内容。为了说明这一点,假设贝西想找到在一个国家一个巨无霸的最小值

某些初始国家和来自其他国家的汇率值可以计算(如下图所示):

*在美国一个巨无霸价值60美元

*美元对加拿大元的汇率是0.2加元/美元

*美元和英镑的汇率是5.00英镑/美元

*从英镑、加元的汇率是0.5加元/英镑

*加元对美元之间的汇率是5.00美元/加元和贝西想找到一个巨无霸的最小可能值在加拿大,可以通过交换货币。有两种方法:

*直接从美元加拿大美元将产生一个汉堡价值60.00美元* 0.2加元/美元= 12.00加元

*从美元英镑60.00加元将产生一个汉堡值得我们* 0.5摄氏度(加元)。

贝西会选择前者,因为她宁愿支付12.00加元,而不是150.00加元在加拿大买一个巨无霸。

贝西有N(1 < = N < = 2000)国家方便标签1到N,她愿意考虑与M的列表(1 < = < = 25000)汇率e_ij(0.1 < e_ij < = 10),每个国家之间我和j(1 < = < = N;1 < = j < = N)。

考虑到价值V(1 < = < = 1000000000000),它不是

一定是一个整数,巨无霸的她开始国家(1 < = < = N),帮她找到一个巨无霸的最小可能值B国(1 < = B < = N;B !=)经过一系列的货币转换。如果没有最低,输出0。

它是保证答案是,如果不是0,1 - 10 ^ 15。它也保证,对任何国家的货币,它是

可能去其他国家的货币。

时间限制:2.0秒

输入输出格式

输入格式:

1号线:五个空格分隔的数字:N,M,V,A,B

行2 . .M + 1:三个空格分隔的数字:i,j,e_ij

输出格式:

1号线:一个正数,巨无霸的价格,绝对或相对误差最多10 ^ 6。如果没有最低,输出0。

输入输出样例

输入样例# 1:

1 2 3 4 60

1 2 0.2

1 3 5 3 2 0.5

2 1 5 输出样例# 1:

12.00