Después de mucho tiempo separados, Alicia y Bob se han reunido. Viven en un país con $n$ ciudades, llamadas creativamente de la ciudad 1 a la ciudad $n$. Bob condujo desde su casa en la ciudad 1 hasta la casa de Alicia en la ciudad $n$.

Cuando Alicia le preguntó a Bob qué camino tomó, se sorprendió al descubrir que no lo recordaba. Bob es eficiente, condujo sin detenerse y sabe que no hay un camino más rápido que el que tomó. También tiene un nuevo TraveLog de la National Adventuring Company (NAC). Cada vez que Bob pasa por una ciudad, el TraveLog registra el tiempo transcurrido desde que salió de la ciudad 1 hasta que llegó a la ciudad actual.

En el diseño anterior, hay dos posibles caminos más rápidos que Bob puede tomar desde la ciudad 1 hasta la ciudad $n$: $1 \to 2 \to 3 \to 5$ o $1 \to 4 \to 5$. Ambos caminos toman un total de 9 unidades de tiempo. El primer camino tendría un TraveLog de 0, 3, 7, 9, y el segundo tendría un TraveLog de 0, 5, 9.

Desafortunadamente, la memoria del TraveLog de Bob está corrupta. Bob cree que algunos de los tiempos se han perdido y los tiempos restantes están mezclados arbitrariamente. Dada la información que queda del TraveLog, ¿puedes reconstruir el camino de Bob?

Entrada

La primera línea de la entrada contiene tres enteros $n$ ($2 \le n \le 2 \cdot 10^5$), $m$ ($1 \le m \le 3 \cdot 10^5$) y $d$ ($1 \le d \le n$), donde $n$ es el número de ciudades en el país, $m$ es el número de carreteras de un solo sentido entre esas ciudades, y $d$ es el número de tiempos que quedan en el TraveLog corrupto de Bob. Las ciudades se identifican por números, del 1 al $n$. Bob vive en la ciudad 1 y Alicia vive en la ciudad $n$.

Cada una de las siguientes $m$ líneas contiene tres enteros $u$, $v$ ($1 \le u, v \le n, u \neq v$) y $h$ ($1 \le h \le 10^6$). Cada línea describe una carretera de un solo sentido desde la ciudad $u$ hasta la ciudad $v$ que toma $h$ unidades de tiempo en recorrerse. Se garantiza que existe al menos un camino desde la ciudad 1 hasta la ciudad $n$. Puede haber varias carreteras entre cualquier par de ciudades.

Cada una de las siguientes $d$ líneas contiene un único entero $t$ ($0 \le t \le 10^{18}$). Esto es lo que queda del TraveLog de Bob. Cada línea es un registro de la cantidad de tiempo que Bob tardó conduciendo desde la ciudad 1 hasta otra ciudad en su camino. Se garantiza que estos valores son distintos.

Salida

El formato de salida depende del número de caminos consistentes con el TraveLog de Bob.

• Si no hay ningún camino consistente con el TraveLog de Bob, imprime 0.
• Si hay múltiples caminos consistentes con el TraveLog de Bob, imprime 1.
• De lo contrario, en la primera línea, imprime el número de ciudades en el camino de Bob. En las líneas siguientes, imprime las ciudades que visitó Bob, una por línea, en el orden en que las visitó.

Ejemplos

Entrada 1

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

Salida 1

3
1
4
5

Entrada 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

Salida 2

1

Entrada 3

2 1 1
1 2 10
5

Salida 3

0

Figure 1. Diagrama de los posibles caminos más rápidos de la ciudad 1 a la ciudad 5.