Mech is writing a routing program for a large computer network. The program has to find the optimal data transfer path between two servers given the description of the whole data communication network. The network is described with a graph: vertices represent servers and arcs between them - communication channels. Each communication channel has two characteristics (time, width), where time - is the time needed to transfer one data packet through the channel, and width is the maximum size of a data packet in the channel. We can define efficiency of a channel to be equal to width / time which shows how much data can be transfered over the channel in a time unit.

Sometimes it is necessary to use intermediate servers for communication. Let's examine data transfer from server A to server B in the network shown below:

It is not possible to transfer data directly so we can use one of the three possible routes in the network (AZB, APQRB or AKLB). Efficiency of a data transfer route over n arcs with characteristics (t₁, w₁), (t₂, w₂), ..., (t_n, w_n) is measured as efficiency = min(w₁, w₂, ..., w_n) / (t₁ + t₂ + ... + t_n). This is due to the fact that we must use packet size of the channel with the least width and the transfer time is equal to the sum of transfer times in consecutive channels.

In the network above efficiency of the three possible routes from A to B equals to:

So we can see that path APQRB is the most efficient. Help Mech to write a program to determine the optimal routing in a given network.

Input

The first line of input contains two integers 2 ≤ n ≤ 100 (number of servers in the network) and 1 ≤ m ≤ 10000 (number of communication channels). The second line contains two integers 0 ≤ A, B < n, A ≠ B - source and destination servers respectively. The following m lines describe the channels. Each channel is described with four integers 0 ≤ x, y < n and 1 ≤ t, w ≤ 10000 meaning that there exists a channel capable of transfering packets of width w in time t from server x to server y. Note that the channels are not bidirectional. There will be at most one channel between any two servers.

Note for Java users: judge data contains large input tests so do not use Scanner as it is very slow.

Output

Output efficiency of the optimal routing rounded to three digits after the decimal point or print No solution if there is no possible data transfer route from server A to server B.

Input:

8 9
1 5
1 0 1 3
0 5 2 1
1 2 3 17
2 3 2 12
3 4 8 20
4 5 7 21
1 6 13 20
6 7 2 17
7 5 25 40

Output:

0.600