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 Xi, Yi, Li, means there is an edge from Xi to Yi, and the length is Li. Li is an even integer. There is a blank line before each test case. 1 <= N <= 103 1 <= M <= 105 1 <= Xi, Yi, A, B <= N 1 <= Li <= 105

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