eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Задача Коммивояжера

Задача Коммивояжера

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Старый мудрый Коммивояжер прожил довольно долгую жизнь, находясь в постоянных разъездах. Он только и занимался тем, что ездил по городам и продавал товары. В коммивояжерских кругах его знали, как главного специалиста по нахождению самых выгодных маршрутов. Еще бы, ведь в свое время ему пришлось изучить метод ветвей и границ для того, чтобы выбирать наименее затратные маршруты.

И вот Коммивояжер решил отправиться в последнюю перед пенсией деловую поездку. Из-за проблем со здоровьем ему пришлось отказаться от идеи побывать во всех N близлежащих городах. Он подумал, что неплохо было бы посетить старых товарищей, которые проживают в некоторых M городах. Остальные города не представляют интереса, и заехать в них можно только, если они лежат на пути следования. Естественно, Коммивояжера интересует самый выгодный маршрут.

Помогите старику организовать последнюю поездку.

Входные данные

В первой строке входного файла два целых числа K (1K100) и N (1N20). Следующие K строк содержат описания дорог. В каждой строке 3 числа – номер пункта отправления, номер пункта назначения и стоимость поездки. Стоимость перемещения по данной дороге одинакова в обоих направлениях. Между двумя пунктами может быть более одной дороги. В следующей строке число M (1M10) – количество городов, которые требуется обязательно посетить хотя бы один раз. В последней строке перечислены номера этих городов. Причем первый город в списке – это город, из которого начинает свой путь Коммивояжер, а последний – в котором заканчивает.

Выходные данные

В выходной файл требуется вывести единственное число - стоимость самого выгодного пути.

Пример

Входные данные #1
3 3
1 2 3
2 3 100
1 3 5
3
1 2 3
Выходные данные #1
11