В городе Фловиль были проведены выборы чиновников. Сам город можно представить в виде связного неориентированного графа, состоящего из вершин и рёбер. Каждое ребро графа задаётся тройкой чисел: (ребро между вершинами и ) - длина ребра.
Каждому чиновнику предоставляется жильё. Чиновнику с номером предоставляется жильё в вершине графа с номером . В городе имеется свободных офисов для работы чиновников. Если чиновнику с номером предоставлен офис в вершине графа с номером , то ежедневно чиновнику необходимо ехать на автомобиле из вершины в вершину . Чиновник обязательно будет ехать по кратчайшему пути. Из всех возможных кратчайших путей он выбирает маршрут по следующему правилу: упорядочим номера вершин маршрута в обратном порядке (т.е. от места работы к дому) и выберем «лексикографически наименьший» путь.
Например, если существуют 2 кратчайших пути из вершины 0 в вершину 5: 0→1→2→4→5 и 0→3→5, то чиновник выберет путь 0→3→5. Т.к. в обратном порядке (от места работы к дому): 5→4→2→1→0 и 5→3→0. А «лексикографически наименьший» - это 5→3→0.
Все дороги (рёбра графа) лежащие вдоль маршрута чиновника всегда будут будут поддерживаться в хорошем состоянии.
Каждому чиновнику необходимо выбрать только один офис из имеющихся в списке так, чтобы суммарная длина дорог, находящихся в хорошем состоянии, была максимальной.
В первой строке через пробел заданы три целых числа , и .
- количество вершин графа ();
- количество рёбер в графе ();
- количество чиновников ();
Далее идут строк, описывающих рёбра графа. Каждое ребро задано в формате: , где - длина ребра (), ().
Далее идёт строка из целых чисел:
- номера вершин, в которых находятся дома чиновников;
Далее идёт строка из T целых чисел:
- номера вершин, в которых находятся офисы для будущей работы чиновников.
- максимальная суммарная длина дорог, которые будут гарантированно отремонтированы.
- номера вершин, в которых находятся офисы для будущей работы чиновников, соответствующие максимальной суммарной длине гарантированно отремонтированных дорог .