Problem D: 最小花费

Problem D: 最小花费

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 5  Solved: 1
[Submit] [Status] [Web Board] [Creator:]

Description

在n个人中,某些人的银行账号之间可以互相转账。这些人之间转账的手续费各不相同。给定这些人之间转账时需要从转账金额里扣除百分之几的手续费,请问A最少需要多少钱使得转账后B收到100元。


Among n individuals, the bank accounts of some people can transfer money to each other. The fees for transferring money between these people vary. Given that when transferring money between these people, there is a percentage of the handling fee that needs to be deducted from the transfer amount, what is the minimum amount A needs to transfer in order for B to receive 100 yuan after the transfer.

 

Input

第一行输入两个正整数n,m,分别表示总人数和可以互相转账的人的对数。(0<n<=2000)
以下m行每行输入三个正整数x,y,z,表示标号为x的人和标号为y的人之间互相转账需要扣除z%的手续费 (z<100)。
最后一行输入两个正整数A,B。数据保证A与B之间可以直接或间接地转账


The first line inputs two positive integers n and m, which represent the total number of people and the pairs of people who can transfer money to each other. (0<n<=2000)

The following m lines input three positive integers x, y, z, which means that the transfer between the person labelled x and the person labelled y needs to deduct z% of the handling fee (z<100).

The last line inputs two positive integers A and B. The data is guaranteed so that transfer directly or indirectly between A and B is possible.

Output

输出A使得B到账100元最少需要的总费用。精确到小数点后8位。


Output the minimum total amount required for person A to transfer person B 100 yuan. Accurate to 8 decimal places.

Sample Input Copy

3 3
1 2 1
2 3 2
1 3 3
1 3

Sample Output Copy

103.07153164