Problem F : Mathematical Marathon

The city of Alexa hosts a marathon every year. The rules of the marathon are simple, the course consists of a
series of N connected checkpoints joined by M roads. Each person starts from a starting checkpoint and must
reach a designated destination checkpoint. Now people need water to run. For each litre of water consumed, a
runner can run 1 kilometer. Each person starts by consuming X litres of water at the starting-point. Water
fountains are available at every checkpoint but there are no water fountains in the middle of the roads.
However this year the problem solver guild's annual olympiad was scheduled on the same day as the
marathon. During this marathon most of the city remains closed, but the people from the guild are refusing to
cancel their event. After much chaos from the guild the city council has agreed to combine the olympiad with
the marathon. Each person running the marathon will now have to solve problems while running.
Each runner will be given a maximum capacity of water that he can drink. This amount will be given before the
race starts and it will be same for every runner. Initially this capacity is X, but after a runner uses a road of
length K, his new capacity becomes Xnew = gcd(Xold , K) so he can only consume Xnew amount of water at that
checkpoint. A runner will not drink more than exactly what is needed to cross a road, even if the maximum
capacity allows it, as the extra weight may slow him down. and as there are no checkpoints in the middle of the
road, so if a road has length K > Xnew he cannot use that road. Given these constraints, the runners have come
to you for help. Help them find the shortest route for their race.

Input

The first line of the input is an integer T, denoting the number of test cases. Each test case starts with a line
consisting of 2 integers N and M which indicate the number of checkpoints and connecting roads respectively.
i-th of the following M lines contain 3 integers Ui , Vi , Wi. Here Ui , Vi indicates the 2 ends of an undirected road, and Wi indicates it's length. There may be multiple roads connecting the same checkpoints. On the last line for
the test case, you are given 3 integers, the starting checkpoint ST, destination checkpoint EN, and the initial
capacity X.

Output

For each test case, print the case number followed by a single integer denoting the length of the shortest path
from the source to the destination, or 'impossible' if there are no valid paths. See sample output for clarification.
Constraints:
● 1 ≤ T ≤ 10
● 1 ≤ N, M, X, Wi ≤ 10^5
● 1 ≤ ST, EN, Ui, Vi ≤ N

Sample Input

2
6 7
1 2 4
1 4 1
2 3 2
2 4 4
3 6 4
4 5 4
5 6 4
1 6 12
5 5
1 2 4
2 3 1
3 5 3
1 4 6
4 5 10
1 5 12

Output for Sample Input

Case 1: 16
Case 2: impossible