403124: GYM101020 H Weekend

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 .

2
4 4 2
1 4 3
1 2 2
2 3 2
3 4 2
2 3
6 8 2
1 2 1
2 3 2
3 6 3
1 4 11
4 5 2
5 6 20
5 3 5
4 3 10
4 5

Case 1: 6
Case 2: 20

in the second test case the shortest path is : 1 > 2 > 3 > 5 > 4 > 5 > 3 > 6