Quieres viajar de Syrjälä a Lehmälä en avión con una ruta de precio mínimo. ¿Qué ciudades visitarás con seguridad?

Entrada

La primera línea de entrada contiene dos enteros ~n~ y ~m~: el número de ciudades y el número de vuelos. Las ciudades están numeradas ~1,2,\ldots,n~. La ciudad ~1~ es Syrjälä y la ciudad ~n~ es Lehmälä. Después, hay ~m~ líneas que describen los vuelos. Cada línea tiene tres enteros ~a~, ~b~ y ~c~: hay un vuelo de la ciudad ~a~ haciaa la ciudad ~b~ con un precio ~c~. Todos los vuelos son de ida. Puedes asumir que existe una ruta de Syrjälä a Lehmälä.

Salida

Primero, imprime un entero ~k~: el número de ciudades que con seguridad están en la ruta. Después, imprime las ~k~ ciudades ordenadas de forma creciente.

Restricciones

• ~1 \leq n \leq 10^5~
• ~1 \leq m \leq 2 \cdot 10^5~
• ~1 \leq a,b \leq n~
• ~1 \leq c \leq 10^9~

Ejemplo de Entrada

5 6
1 2 3
1 3 4
2 3 1
2 4 5
3 4 1
4 5 8

Ejemplo de Salida

4
1 3 4 5