Дорога до школи#5486

Дорога до школи

2 секунди

64 мегабайти

Середня

Місто нафтовиків складається з $N$ пронумерованих площ, деякі пари яких з'єднано вулицями з відомою довжиною. Вулиця не може з'єднувати площу саму з собою, і кожною вулицею можна рухатися у двох напрямках. Між будь-якою парою площ існує не більш однієї вулиці.

З історичних причин усі будинки мешканців і установи міста розміщуються лише на площах. Зокрема, школа знаходиться на площі з номером $1$ . За давньою традицією багато школярів ходять до школи разом. $K$ хлопців із одного класу вирішили не порушувати цю традицію. Але, оскільки їхні будинки розташовано на різних площах, їм доводиться частину шляху йти окремо. Через кліматичні умови кожен з них добирається від будинку до школи лише найкоротшим шляхом.

Потрібно написати програму, яка визначає найбільшу відстань, яку хлопці можуть пройти разом.

Вхідні дані

У першому рядку вхідного файлу записано три цілі числа: $N$ , $M$ та $K$ ( $1 \leq N \leq 1000$ 1 \leq N \leq 1000, $1 \leq M \leq 10000$ 1 \leq M \leq 10000, $1 \leq K \leq 100$ 1 \leq K \leq 100), де $N$ — кількість площ у місті, $M$ — кількість доріг, а $K$ — кількість однокласників. У другому рядку містяться $K$ натуральних чисел від $1$ до $N$ , які визначають номери площ, на яких розташовано будинки $K$ однокласників. Далі у $M$ рядках описані дороги. Кожна дорога задається трійкою чисел — номерами з'єднаних площ і довжиною. Довжина є натуральним числом, не більшим за $1000$ . Усі числа у рядках розділені пропусками. Гарантується, що кожен із $K$ школярів може дійти від будинку до школи дорогами, наявними у місті.

Вихідні дані

У вихідний файл необхідно вивести найбільшу відстань, яку однокласники зможуть пройти разом на шляху від своїх будинків до школи.

Приклади

Приклад 1