Maximum Aesthetic Value

Lara has a beautiful garden divided into N sections. There are M paths connecting these sections, and each path has an aesthetic value v and a depreciation factor d. Depending on the path type, the path may be one-way or bidirectional. When Lara traverses a path as the k-th move, the effective aesthetic value she gains from that path is:

\(v \times (1-d)^{k}\)

Your task is to help Lara determine the maximum total aesthetic value she can accumulate when traveling from section s to section t. If there is no valid path, output 0.000000. The answer should be printed with six digits after the decimal point.

Note: A path with type 1 is one-way (from a to b) while a path with type 2 is bidirectional.

inputFormat

The first line contains two integers N and M separated by a space, representing the number of sections in the garden and the number of paths, respectively.

The following M lines each contain five values: integers a and b, a floating-point number v, a floating-point number d, and an integer path_type. Here, a and b denote the connected sections, v is the aesthetic value, d is the depreciation factor, and path_type indicates the direction (1 for one-way from a to b, 2 for bidirectional).

The last line contains two integers s and t, which are the starting and target sections.

outputFormat

Output a single line containing the maximum total aesthetic value Lara can achieve when traveling from section s to section t. The value must be printed with six digits after the decimal point.

3 3
0 1 10 0.1 2
1 2 20 0.2 1
0 2 15 0.05 1
0 2

15.000000