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

Изменение сценария

Изменение сценария

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

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

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

Первая строка содержит три числа n, m и k~(1 \le k \le n \le 10^4, 0 \le m \le 10^6), где n количество перекрестков, m количество улиц в городе, а k количество перекрестков которые Вы проезжаете каждый день.

Следующая строка содержит k целых чисел — индексы (начиная с 1) перекрестков которые Вы проезжаете каждый день. Первым перекрестком в этом списке всегда будет 1, а последним всегда будет n. Это будет именно кратчайший путь между 1 и n, проходящий по k перекресткам.

Далее идут m строк. i-ая строка содержит три целых числа a_i, b_i, c_i и описывают улицу от перекрестка a_i до перекрестка b_i длиной c_i~(1 \le a_i, b_i \le n, 1 \le c_i \le 10^4). Все улицы двунаправленные.

Между одной парой перекрестков может существовать несколько улиц. Кратчайший путь для каждой соседней пары перекрестков a и b использует улицу минимальной длины от a до b.

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

Вывести "yes" если существует другой путь такой же длины и "no" иначе.

Пример

Входные данные #1
3 3 3
1 2 3
1 2 1
2 3 2
1 3 3
Выходные данные #1
yes
Входные данные #2
4 5 2
1 4
1 2 2
2 4 1
1 3 1
3 4 2
1 4 2
Выходные данные #2
no
Источник 2015 German Collegiate Programming Contest (GCPC), June 20, Problem E