Roads of Manchester

Every road in Manchester is a one-way directed road. Each road has a limit on how many cars can pass through it in one hour. The capacity of a path is the minimum road limit among all roads on that path.

The redundancy ratio from A to B is the quotient of two values. The numerator is the maximum number of cars that can reach B in one hour when all available A-to-B paths may be used at the same time. The denominator is the maximum number of cars that can reach B in one hour when only one path is used.

To minimize this ratio, the single-path value in the denominator must be as large as possible. In other words, use the A-to-B path whose capacity is maximum among all A-to-B paths.

Given the road information and vertices A and B, compute the minimum redundancy ratio.

The first line contains the number of test cases T (1 ≤ T ≤ 1,000). Each test case has the following format.

The first line of a test case contains four integers N, E, A, and B, in that order. N (2 ≤ N ≤ 1,000) is the number of vertices in the graph, and E (E ≥ 1) is the number of edges. A (0 ≤ A < N) and B (0 ≤ B < N, A ≠ B) are the source and destination vertices.

The next E lines each contain the information for one road as U V W. U (0 ≤ U < N) and V (0 ≤ V < N, V ≠ U) mean that the road goes from U to V, and W (1 ≤ W ≤ 1000) is the maximum number of cars that can pass through that road in one hour.

For each test case, print the minimum redundancy ratio on its own line. Print the value rounded to exactly three digits after the decimal point.