You and your friends are going to camping next weekend , because you are the best driver and you are living in this town for ten years , you have to drive the car from your home and pick up each of your friends to take them with you ,then finally go to the camping site. You have the map of the town and the length of every street ,and homes of friends will be at some intersections. you want to start from your home then pick up all of your friends then go to the camping site as fast as you can so you have to find the shortest path to do that. you can pick up your friends in any order but you have to make sure you pick up all of them. NOTE: you can pass by any intersection more than once including home and camping site .
Your program will be tested on one or more test cases. The first line of the input will be a single integer T, the number of test cases (1 ≤ T ≤ 50). Followed by the test cases, the first line of each test case contains three integers N,M,F (3 ≤ N ≤ 100 , 0<M ≤ (N*(N-1))/2 , 1 ≤ F ≤ 9 ) representing the number of intersections , the number of streets and number of friends respectively. Followed by M lines, each line contains 3 integers separated by a single space X Y Z (1 ≤ X, Y ≤ N), (1 ≤ Z ≤ 1000) which represent a street between intersection X and intersection Y with length Z in both direction (X and Y will be different). then follow F (1<fr<N) deferent integer representing friends home number(number of intersection where home is located). your home is at intersection number one and camping site is at intersection number N.
For each test case print a single line containing "Case n:" (without quotes) where n is the test case number (starting from 1) followed by a space then the shortest path to go from your home to camping site after picking up all your friends .
in the second test case the shortest path is : 1 > 2 > 3 > 5 > 4 > 5 > 3 > 6
## Input
Your program will be tested on one or more test cases. The first line of the input will be a single integer T, the number of test cases (1 ≤ T ≤ 50). Followed by the test cases, the first line of each test case contains three integers N,M,F (3 ≤ N ≤ 100 , 0<M ≤ (N*(N-1))/2 , 1 ≤ F ≤ 9 ) representing the number of intersections , the number of streets and number of friends respectively. Followed by M lines, each line contains 3 integers separated by a single space X Y Z (1 ≤ X, Y ≤ N), (1 ≤ Z ≤ 1000) which represent a street between intersection X and intersection Y with length Z in both direction (X and Y will be different). then follow F (1<fr<N) deferent integer representing friends home number(number of intersection where home is located). your home is at intersection number one and camping site is at intersection number N.
## Output
For each test case print a single line containing "Case n:" (without quotes) where n is the test case number (starting from 1) followed by a space then the shortest path to go from your home to camping site after picking up all your friends .
[samples]
## Note
in the second test case the shortest path is : 1 > 2 > 3 > 5 > 4 > 5 > 3 > 6
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case, let $ n, d, r \in \mathbb{Z}^+ $ denote:
- $ n $: the circumference (length) of the circular river,
- $ d $: David’s speed (meters per minute),
- $ r $: Roger’s speed (meters per minute).
Both start at position 0 at minute 0. At the beginning of minute $ t \geq 1 $, each places a marker at their current position modulo $ n $.
**Constraints**
$ 1 \leq T \leq 10^5 $, and for each test case:
$ 1 \leq n, d, r \leq 10^5 $
**Objective**
Find the smallest positive integer $ t $ such that:
$$
(t \cdot d) \bmod n = (t \cdot r) \bmod n
$$
That is, the first minute $ t \geq 1 $ where David and Roger occupy the same position on the circular river.