Город нефтяников состоит из N
пронумерованных площадей, некоторые пары которых соединены улицами. Длина
каждой улицы известна. Известно также, что не существует такой улицы, которая
соединяет площадь саму с собой. По любой улице можно двигаться в двух
направлениях, между любой парой площадей существует не более одной улицы.
По историческим причинам все дома жителей и учреждения
города размещаются только на площадях. В частности, школа находится на площади
с номером 1. По давно устоявшейся в городе традиции многие школьники стараются
ходить в школу вместе. K ребят из одного класса
решили этой традиции не изменять, но так как их дома расположены на разных
площадях, то какую-то часть пути они всё равно проходили порознь. Более того, в
силу климатических условий, каждый из них добирался от дома до школы только
кратчайшим путём.
Требуется написать программу, которая вычисляет
наибольшее расстояние, которое ребята могут пройти вместе.
Формат входных данных:
В первой строке входного файла записаны три целых числа, N, M и K (1 £ N £ 1000; 1 £ M £ 10 000; 1 £ K £ 100), где N — количество
площадей в городе, M — количество дорог, а K — количество одноклассников. Во
второй строке содержатся K натуральных чисел от
1 до N, определяющих номера площадей, на которых
расположены дома K одноклассников. Далее в M строках описаны дороги. Каждая дорога задаётся тройкой
чисел — номерами соединённых площадей и длиной. Длина является натуральным
числом, не превосходящим 1000. Все числа в строках разделены пробелами.
Гарантируется, что любой из K школьников
может дойти от дома до школы по имеющимся в городе дорогам.
Формат выходных данных:
В выходной файл необходимо вывести наибольшее расстояние,
которое одноклассники смогут пройти вместе по пути от своих домов до школы.
Примеры файлов входных и выходных данных:
|
INPUT
|
OUTPUT
|
|
4 5 2
2 3
1 4 1
4 2 1
4 3 1
1 2 2
1 3 2
|
1
|
|
4 5 2
2 3
1 4 1
4 2 1
4 3 1
1 2 1
1 3 1
|
0
|
