Jack finally meets a girl, and today is their first date. The city they live in consists of n vertices and m bidirectional roads. Each road has a standard time to pass through and an influence factor . Every day there is a congestion factor a, which is a uniformly distributed random variable between [0,1]. The time needed to pass the i-th road is . Note that is always not less than .

Jack wants to calculate the of minimum time between his home and their date place .

The first line contains four integers , , ,  (, , ) --- the number of vertices, the number of roads, Jack's home, and Jack's date place, respectively.
The following  lines describe roads. Each line contains four integers , , ,  (, , ) --- denotes that there is a road between  and , whose factors are  and .

Output a real number --- the expected value of minimum time between  and .
The output is considered correct if it has an absolute error of at most .

2 1 1 2 
1 2 2 1

2.5