После долгой разлуки Алиса и Боб воссоединились. Они живут в стране с $n$ городами, творчески названными от города 1 до города $n$. Боб ехал из своего дома в городе 1 в дом Алисы в городе $n$.

Когда Алиса спросила Боба, каким путем он ехал, он был ошеломлен, обнаружив, что не помнит. Боб эффективен, он ехал без остановок и знает, что нет пути быстрее того, который он выбрал. У него также есть совершенно новый журнал путешествий (TraveLog) от Национальной приключенческой компании (NAC)! Каждый раз, когда Боб проезжает через город, журнал записывает время, прошедшее с момента, когда он покинул город 1, до момента, когда он прибыл в текущий город.

На схеме ниже показаны два возможных кратчайших пути, по которым Боб мог проехать из города 1 в город $n$: $1 \to 2 \to 3 \to 5$ или $1 \to 4 \to 5$. Оба пути занимают в общей сложности 9 единиц времени. Первый путь имел бы записи в журнале 0, 3, 7, 9, а второй — 0, 5, 9.

К сожалению, память в журнале Боба повреждена. Боб считает, что некоторые значения времени пропали, а оставшиеся перемешаны в произвольном порядке. Можете ли вы восстановить путь Боба по тому, что осталось в журнале?

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

Первая строка входных данных содержит три целых числа $n$ ($2 \le n \le 2 \cdot 10^5$), $m$ ($1 \le m \le 3 \cdot 10^5$) и $d$ ($1 \le d \le n$), где $n$ — количество городов в стране, $m$ — количество дорог с односторонним движением между этими городами, а $d$ — количество временных меток, оставшихся в поврежденном журнале Боба. Города пронумерованы от 1 до $n$. Боб живет в городе 1, а Алиса — в городе $n$.

Каждая из следующих $m$ строк содержит три целых числа $u, v$ ($1 \le u, v \le n, u \neq v$) и $h$ ($1 \le h \le 10^6$). Каждая строка описывает дорогу с односторонним движением из города $u$ в город $v$, прохождение которой занимает $h$ единиц времени. Гарантируется, что существует хотя бы один путь из города 1 в город $n$. Между любой парой городов может быть несколько дорог.

Каждая из следующих $d$ строк содержит одно целое число $t$ ($0 \le t \le 10^{18}$). Это то, что осталось от журнала Боба. Каждая строка — это запись количества времени, которое Боб затратил на путь из города 1 до другого города на своем маршруте. Гарантируется, что эти значения различны.

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

Формат вывода зависит от количества путей, соответствующих журналу Боба.

• Если нет пути, соответствующего журналу Боба, выведите 0.
• Если журналу Боба соответствует несколько путей, выведите 1.
• В противном случае, в первой строке выведите количество городов на пути Боба. В последующих строках выведите города, которые посетил Боб, по одному в строке, в порядке их посещения.

Примеры

Пример 1

5 5 2
1 2 3
2 3 4
3 5 2
1 4 5
4 5 4
5
9

3
1
4
5

Пример 2

6 8 2
1 2 1
2 3 2
3 6 8
1 4 3
4 5 4
5 6 4
5 2 7
1 6 13
0
3

1

Пример 3

2 1 1
1 2 10
5

0