eolymp
bolt
Try our new interface for solving problems
Problems

Dima and a famous tourist

Dima and a famous tourist

Time limit 1 second
Memory limit 256 MiB

Знаменитый турист Геннадий всегда использует кратчайшие пути в своих путешествиях. Мальчик Дима является поклонником Геннадия и собирает всю информацию, которую он может найти о нём — вырезки из газет, новости из Интернета и т.п.

Недавно Геннадий совершил путешествие. В некоторых городах по дороге его видели поклонники и оставляли об этом запись в своем блоге. Дима нашел все эти упоминания, но так как свой поиск он проводил уже по окончании путешествия, он не смог восстановить хронологический порядок записей — он знает лишь набор городов, в которых Геннадий точно побывал. Ему точно известно, что Геннадий путешествовал из какого-то города в какой-то другой по кратчайшему пути. Помогите Диме построить один из возможных путей Геннадия.

Дима пользуется только проверенными источниками, так что путь гарантированно существует.

Input data

Первая строка содержит 2 целых числа n и m (1n, m10^5) — количество городов и дорог соответственно. Каждая из последующих m строк содержит описание одной дороги a_i, bi, t_i (a_ib_i, 1a_i, b_in, 1t_i10^4) — города на концах дороги и время путешествия по ней. В следующей строке содержится k — количество городов, которые точно посетил Геннадий. В последней строке содержится k чисел — номера этих городов. Каждый город в этом списке встречается не более одного раза.

Output data

В первой строке выведите количество дорог, на которых побывал Геннадий, а во второй — эти дороги в порядке посещения Геннадием. В случае, если существует несколько решений — выведите любое.

Examples

Input example #1
6 6
1 2 2
2 6 2
1 3 1
3 4 1
4 5 1
5 6 1
3
5 1 3
Output example #1
3
3 4 5
Author Egor Kulikov
Source Winter School Kharkov 2012