Route Redundancy
A city is made up exclusively of one-way streets. Each street in the city has a capacity, which is the minimum of the capacities of the streets along that route.
The redundancy ratio from point A to point B is the ratio of the maximum number of cars that can get from point A to point B in an hour using all routes simultaneously, to the maximum number of cars that can get from point A to point B in an hour using one route. The minimum redundancy ratio is the number of capacity of the single route with the largest capacity.
Input
The first line of input contains asingle integer P (1 ≤ P ≤ 1000), which is the number of data sets that follow.Each data set consists of several lines and represents a directed graph with positive integer weights.
The first line of each data set contains five apace separatde integers. The first integer D is the data set number. The second integer,N(2<=N<=1000),is the number of nodes inthe graph. The thied integer E (E ≥ 1) is the number of edges in the graph. The fourth integer A (0 ≤ A < N) is the index of point A. The fifth integer B (0 ≤ B < N, A ≠ B) is the index of point B.
The remaining E lines desceibe each edge. Each line contains three space separated in tegers. The first integer U (0 ≤ U < N) is the index of node U. The second integer V (0 ≤ V < N, V ≠ U) is the node V. The third integer W (1 ≤ W ≤ 1000) is th capacity (weight) of path from U to V.
Output
For each data set there is one line of output. It contains the date set number(N) follow by a single space, followed by a floating-point value which is the minimum redundancy ratio to 3 digits after the decimal point.