A communication network is represented as a cycle-free, not necessarily simple, weighted, directed graph. The weight, r(e), of an edge e is a real number in the interval [0, 1] representing the reliability of the communication channel represented by the edge. The reliability of a communication channel is interpreted as the probability that the channel will not fail. We assume that all probabilities are independent. There could be more than one channel between the same two nodes, in the same direction. Give an efficient algorithm to find the most reliable path from a given source node to a given destination node. What is the worst-case time complexity of your algorithm?

The first line of input will contain the number of nodes in the network N and the number of edges in the network E (2 <= N, E <= 30,000).

The second line of input will contain s and d, the source and the destination.

Each of the next E lines will contain a, b, c  (1 <= a, b <= N, 0 <= c <= 1), indicating that there is a directed edge from node a to node b with reliability c.

Output

Print to the ouput a single floating point number r, denoting the reliability of the best path from s to d. r should contain exactly 6 digits after the decimal point.

Example

Input:

4 6
1 4
1 2 0.75
1 2 0.5
2 3 1
2 4 0.75
1 3 1.0
3 4 0.25

Output:

0.562500