Description

Among $n$ people, certain pairs can transfer money between their bank accounts. The transfer fee between these people can differ from pair to pair. Given, for each such pair, the percentage fee that will be deducted from the transferred amount, determine the minimum amount $A$ must have so that after the transfers $B$ receives $100$ yuan.

Input Format

The first line contains two positive integers $n,m$, representing the total number of people and the number of pairs who can transfer money to each other.

Each of the following $m$ lines contains three positive integers $x,y,z$, meaning that transferring money between person $x$ and person $y$ incurs a fee of $z\%$ deducted from the transferred amount $(z<100)$.

The last line contains two positive integers $A,B$. The testdata guarantees that $A$ and $B$ can transfer money directly or indirectly.

Output Format

Output the minimum total amount that $A$ needs so that $B$ receives $100$ yuan. Print to 8 digits after the decimal point.

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

103.07153164

Hint

$1\le n \le 2000,m\le 100000$.

It is guaranteed that the answer does not exceed $10^4$.

Translated by ChatGPT 5