The Traveling Salesman Problem
The wise old Salesman, known for his extensive travels and expertise in finding the most profitable routes, is planning one final business trip before retiring. Over the years, he mastered the branch and bound method to identify the least costly paths. However, due to health concerns, he has decided to limit his journey to visiting only M specific cities where his old friends reside, out of N nearby cities. Other cities are of interest only if they lie along the travel route. Naturally, he seeks the most cost-effective route for this trip.
Your task is to help the Salesman plan this last journey.
Input
The first line of the input contains two integers: K (1 ≤ K ≤ 100) and N (1 ≤ N ≤ 20). The following K lines describe the roads, with each line providing three numbers: the starting city number, the destination city number, and the travel cost. The cost is the same in both directions, and there may be multiple roads between two cities. The next line contains the integer M (1 ≤ M ≤ 10), representing the number of cities that must be visited at least once. The final line lists these cities' numbers, with the first city being the starting point and the last city being the destination.
Output
The output should be a single number representing the cost of the most profitable route.