You are a truck driver that needs to deliver some cargo from one city to another. To accomplish this you are going to use the road network. A road connects exactly 2 cities. Not all cities are directly connected. For example if you want to get from the city A to the city B but the only roads that exist connect A with C and B with C then you will have to pass through the city C. Between 2 cities there is at most one road. Roads may always be used in both direction. Don't make any further assumptions about the topology of the road network. To pass a road you have to pay a tax of x€. All roads cost the same regardless of their length.
How much do you have to pay at least to complete your trip?
The input begins with a single positive integer T on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.
Each test case starts with a line containing 5 positive integers: x, n, m, s and t.
After that the test case contains m lines each describing a road using its 2 end cities.
The output should contain exactly T lines. The t-th line should contain the the amount you have to pay for the t-th testcase or -1 if you can't reach the city t. A line ends per definition with a newline character.
3 3 3 2 1 2 1 3 3 2 100 5 6 4 3 1 3 2 4 5 1 3 2 4 1 2 5 42 6 6 1 6 1 2 2 3 3 1 4 5 5 6 6 4
6 200 -1