All of you must have heard the name of The Lord of the Rings. As we know that the ring, that was said to be the lord of the rings, was destroyed by Frodo Baggins in the mountain of doom. And so, the evil spirit Sauron was not able to capture the ring and was finally destroyed. After defeating Sauron’s army, Aragorn became the king and with his coronation the world moved into the dominion of Men. And they lived happily ever after. But thats not actually the whole story. Defeating Sauron was not the final victory over “evil” as such. Because the evil dark lord and Sauron’s master — Morgoth can still recover, grow and take shape again. After the death of Sauron, many years have passed. Aragorn is old now and his son Eldarion is the king. Things were going fine except one day they discovered the fact that Morgoth has recovered his powers and is planning to take over the world. The whole middle Earth is again waiting for another war. Eldarion has made several plans with the wise council to stop Morgoth. They have the map, so they are aware of the fact that there are some territories in Middle-Earth. Many two-way roads exist between some pairs of territories. The times to travel all roads are known to them. To go from a territory to another one, they can use one or more roads. And all territories are reachable from any territory. That’s why they have the fear that if Morgoth’s army enters to any territory then they can invade any territory they want. To protect a road, huge number of armies has to be placed there. Eldarion is a man of honor like his father. So, he doesn’t want to leave any territory unguarded or weak. But since his armies are little in number compared to Morgoth’s, he is at a loss. Cause if he sends armies to protect the roads then they may win, but some territories might go down. But if he sends the armies to protect the territories, then if any territory goes down, more will be in danger because Morgoth’s army will forward their march using the unguarded roads and of course they can capture roads and can hamper the communication amongst territories. But if Eldarion places armies to protect both roads and territories then both roads and territories will be weak since the number of armies protecting a territory or a road will be too low to fight against Morgoth’s army. After a long discussion, they have got many ideas, but no idea fascinated Eldarion. So, he went to his father, Aragorn — the old king. Aragorn took a day to think, and the next day he told his son about his idea. The idea is to keep as fewer roads as possible such that the armies can still be sent from any territory to all other territories. Rest of the roads will be destroyed. As they have many trebuchets and catapults, they can destroy roads easily and without heavy effort. After that they will pick some territories that have the higher chances to be attacked first. These territories will be selected by Aragorn himself from his past experience in battles, and these are called the prime territories. All the armies will be assigned to protect these territories only. When a territory is under attack, either prime or non-prime, the informers in this territory will seek help from a prime territory. This helping territory will be randomly chosen. After the arrival of the armies, the informers will seek help from another randomly chosen prime territory. And they will continue seeking help until armies from all the prime territories come. The informers will always choose a new prime territory for seeking help. So, the estimated time for a territory is the total required time for armies from all prime

2/2 territories to reach this territory. And the Total estimated time is the summation of estimated times of all territories. You can assume that the time to inform other territories is negligible. Now, they are planning to use Aragorn’s idea. So, they want to keep the roads such that the Total estimated time is as low as possible. You are one of the head councilors and you know the map fully. Now you have to find the minimum Total estimated time. Remember that the whole middle earth is depending on you. Input The first line of the input will contain T (≤ 100), denoting the number of cases. Each case starts with a blank line. The next line will contain three integers n (2 ≤ n ≤ 16), m and k (1 ≤ k ≤ n), where n is the number of territories, m is the total number of roads and k is the number of prime territories. The territories are numbered from 0 to n − 1. The next line contains k integers separated by spaces. These integers denote the prime territories. Each of the next m lines will contain three integers u, v (0 ≤ u, v < n and u ̸= v) and w (1 ≤ w ≤ 1000) denoting that there is a two way road between territory u and v and the time to cross this road is w minutes. You can assume that all the roads are valid, no road is listed more than once and multiple roads between same pair of territories don’t exist. Output For each case, print the case number and the minimum Total estimated time. Sample Input 2 321 0 012 125 332 02 012 125 0 2 50 Sample Output Case 1: 9 Case 2: 21