Задачи
Задача Коммивояжера
Задача Коммивояжера
Старый мудрый Коммивояжер прожил довольно долгую жизнь, находясь в постоянных разъездах. Он только и занимался тем, что ездил по городам и продавал товары. В коммивояжерских кругах его знали, как главного специалиста по нахождению самых выгодных маршрутов. Еще бы, ведь в свое время ему пришлось изучить метод ветвей и границ для того, чтобы выбирать наименее затратные маршруты.
И вот Коммивояжер решил отправиться в последнюю перед пенсией деловую поездку. Из-за проблем со здоровьем ему пришлось отказаться от идеи побывать во всех \textbf{N} близлежащих городах. Он подумал, что неплохо было бы посетить старых товарищей, которые проживают в некоторых \textbf{M} городах. Остальные города не представляют интереса, и заехать в них можно только, если они лежат на пути следования. Естественно, Коммивояжера интересует самый выгодный маршрут.
Помогите старику организовать последнюю поездку.
\InputFile
В первой строке входного файла два целых числа \textbf{K} (\textbf{1} ≤ \textbf{K} ≤ \textbf{100}) и \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{20}). Следующие \textbf{K} строк содержат описания дорог. В каждой строке 3 числа -- номер пункта отправления, номер пункта назначения и стоимость поездки. Стоимость перемещения по данной дороге одинакова в обоих направлениях. Между двумя пунктами может быть более одной дороги. В следующей строке число \textbf{M} (\textbf{1} ≤ \textbf{M} ≤ \textbf{10}) -- количество городов, которые требуется обязательно посетить хотя бы один раз. В последней строке перечислены номера этих городов. Причем первый город в списке -- это город, из которого начинает свой путь Коммивояжер, а последний -- в котором заканчивает.
\OutputFile
В выходной файл требуется вывести единственное число - стоимость самого выгодного пути.
Входные данные #1
3 3 1 2 3 2 3 100 1 3 5 3 1 2 3
Выходные данные #1
11