Resistance

Recently DRD got a number of wires. Some of the wires have the resistance 1 ohm while the others have the resistance 0 ohm. Each wire has probability 50% to be 0 ohm or 1 ohm.

Now ATM gets a circuit board. There are N points in the circuit board. DRD wants to connect these points using his wires. He chooses a wire randomly and chooses two points in the board randomly. Then he will connect the two points using the wire he chooses. DRD will use M wires. Note that it's possible that there exist two points which are not connected by wires.

ATM is interested in the equivalent resistance between the point S and point T. Since they lack of instruments, they want you to calculate the answer.

The first line contains an integer T, denoting the number of the test cases.

For each test case: The first line contains 4 integers: N, M, S, and T. For each of the next M lines, it contains 3 integers: u, v, and c, representing that DRD uses a wire, whose resistance is c, to connect the point u and v. It's guaranteed that 1 <= N <= 10000 and M = 4*N. 1 <= u, v <= N. c is randomly chosen from {0, 1} and u and v are randomly chosen from {1, 2, ..., N}. Note that u can equal v.

For each test case, output a real number. There must be exactly 6 digits after the decimal point. If S and T are not connected by wires, output "inf" (without quotes) instead.

2
10 40 6 1
9 4 1
7 3 1
10 1 0
5 2 0
6 7 1
7 3 1
3 5 1
3 6 1
8 10 0
8 3 0
7 3 1
3 9 1
2 8 1
10 5 0
10 2 1
10 9 1
9 1 0
7 5 1
10 2 0
8 1 0
2 8 0
10 2 0
1 5 0
5 4 0
7 4 1
8 5 1
4 3 1
6 1 1
5 10 0
3 9 1
5 1 0
9 2 1
3 4 1
5 8 0
3 5 1
3 4 1
2 7 0
4 4 0
1 8 0
10 10 0
10 40 2 1
5 6 1
8 10 1
3 8 1
8 5 0
6 4 1
9 9 1
3 6 1
2 4 1
9 8 0
9 3 0
7 7 1
8 6 1
10 4 1
1 3 0
2 8 1
9 8 0
8 1 1
6 4 0
3 4 0
1 4 0
1 10 0
9 10 0
6 1 1
3 1 1
5 4 0
1 2 1
7 2 1
10 9 0
6 1 0
10 3 1
8 6 1
1 4 0
1 1 0
4 3 0
1 8 0
7 10 1
10 6 0
4 5 0
2 2 0
4 2 1

0.333333
0.222222

2014 ACM/ICPC Asia Regional Anshan Online