Зміна сценарію
Зміна сценарію
Каждый день Вы едете на работу, используя дороги самого короткого пути. Это эффективно, но со временем Вам надоедает смотреть на одни и те же здания и перекрестки каждый день. Вы решаете искать другие маршруты. Конечно, Вы не хотите жертвовать временем, так что новый путь должен быть столь же коротким как и старый. Существует ли другой путь, который отличается от старого, хотя бы одной улицей?
\InputFile Первая строка содержит три числа $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$.
\OutputFile Вывести "yes" если существует другой путь такой же длины и "no" иначе.
\includegraphics{https://static.e-olymp.com/content/e3/e312bc38254a215cc7dbc0daaf1726d1e57d1c3b.gif}
3 3 3 1 2 3 1 2 1 2 3 2 1 3 3
yes
4 5 2 1 4 1 2 2 2 4 1 1 3 1 3 4 2 1 4 2
no