Дима и знаменитый турист
Знаменитый турист Геннадий всегда использует кратчайшие пути в своих путешествиях. Мальчик Дима является поклонником Геннадия и собирает всю информацию, которую он может найти о нём — вырезки из газет, новости из Интернета и т.п.
Недавно Геннадий совершил путешествие. В некоторых городах по дороге его видели поклонники и оставляли об этом запись в своем блоге. Дима нашел все эти упоминания, но так как свой поиск он проводил уже по окончании путешествия, он не смог восстановить хронологический порядок записей — он знает лишь набор городов, в которых Геннадий точно побывал. Ему точно известно, что Геннадий путешествовал из какого-то города в какой-то другой по кратчайшему пути. Помогите Диме построить один из возможных путей Геннадия.
Дима пользуется только проверенными источниками, так что путь гарантированно существует.
Входные данные
Первая строка содержит 2 целых числа n и m (1 ≤ n, m ≤ 10^5) — количество городов и дорог соответственно. Каждая из последующих m строк содержит описание одной дороги a_i, bi, t_i (a_i ≠ b_i, 1 ≤ a_i, b_i ≤ n, 1 ≤ t_i ≤ 10^4) — города на концах дороги и время путешествия по ней. В следующей строке содержится k — количество городов, которые точно посетил Геннадий. В последней строке содержится k чисел — номера этих городов. Каждый город в этом списке встречается не более одного раза.
Выходные данные
В первой строке выведите количество дорог, на которых побывал Геннадий, а во второй — эти дороги в порядке посещения Геннадием. В случае, если существует несколько решений — выведите любое.