Time Limit: 2000 MS Memory Limit: 65536 K

## Description

There is a directed graph with N nodes and M edges.
You can do an operation that
find an edge, and make its length L half, to L/2.
You can only do the operation one time.
Can you find the shotest route from A to B?
## Input

The first line of input is the number of test case.
For each test case:
The first line contains four integers N, M, A and B.
The next M lines each contains three integers X_{i}, Y_{i}, L_{i},
means there is an edge from X_{i} to Y_{i}, and the length is L_{i}.
L_{i} is an even integer.
There is a blank line before each test case.
1 <= N <= 10^{3}
1 <= M <= 10^{5}
1 <= X_{i}, Y_{i}, A, B <= N
1 <= L_{i} <= 10^{5}
## Output

For each test case output the answer on a single line.
If you can not go from A to B, just output "-1".
## Sample Input

4
2 1 1 2
2 1 6
4 4 1 4
1 2 8
2 4 8
1 3 2
3 4 18
4 4 1 4
1 2 8
2 4 8
1 3 2
3 4 50
1 1 1 1
1 1 6
## Sample Output

-1
11
12
0
## Source

8th SCUPC
## Author

windy7926778