Eren se ha infiltrado en Marley, como todos sabemos Marley es el enemigo de su pais, por ello su primera tarea es evaluar su red de telecomunicaciones, recopilar informacion y enviársela a sus superiores. Después de mapear toda la red, que consta de switches de red y cables entre ellos, tiene la corazonada de que, no solo algunos de los switches son redundantes, ¡algunos de ellos no se utilizan en absoluto! Antes de presentarle esto a su jefe, decide pedirle a usted que cree un programa para probar sus afirmaciones. Los datos que ha recopilado consisten en el mapa de la red, así como la longitud de cada cable. Si bien no sabe el tiempo exacto que se tarda en enviar un paquete de red a través de cada cable, sabe que se puede calcular como ~l/ v + c~, donde:

• ~l~ es la longitud del cable.
• ~v~ es la velocidad de propagación de el cable.
• ~c~ es la sobrecarga de transmitir el paquete dentro y fuera del cable.

No ha podido medir ~v~ y ~c~. Lo único que sabe sobre ellos es que son números reales que satisfacen ~v > 0~ y ~c \ge 0~, y que son iguales para todos los cables. También sabe que cuando un paquete de red se transmite de un switch a otro, los algoritmos de enrutamiento de la red asegurarán que el paquete tome una ruta óptima, una ruta que minimice el tiempo total de tránsito.

Dado el mapa de la red y la longitud de cada cable, determine qué switches nunca podrían ser parte de una ruta óptima al transmitir un paquete de red desde el conmutador ~1~ al conmutador ~n~, sin importar cuáles sean los valores de ~v~ y ~c~.

Calificación:

• ~10~ puntos: Se cumple que ~N\leq10~.
• ~30~ puntos: Se cumple que ~N\leq500~
• ~5~ puntos: El grafo dado es un arbol generado aleatoriamente.
• ~5~ puntos: El grafo dado forma un círculo.
• El resto de puntos sin restricciones adicionales.

Entrada:

La entrada consta de:

• Una línea con dos números enteros ~n, m (2 \le n \le 2000, 1 \le m \le 10^4)~, el número de switches y el número de cables en la red. Los switches están numerados del ~1~ al ~n~.
• ~m~ líneas, cada una con tres números enteros ~a~, ~b~ y ~l~ ~(1 \le a, b \le n, 1 \le l \le 10^9)~, que representan un cable de red de longitud ~l~ que conecta los switches ~a~ y ~b~. Hay como máximo un cable que conecta un par determinado de switches y ningún cable conecta un switch a sí mismo. Se garantiza que existe una ruta entre cada par de switches.

Salida:

Primero genera una línea con un número entero ~k~, el número de switches que nunca podrían ser parte de una ruta óptima cuando se transmite un paquete desde el switch ~1~ al switch ~n~. Luego, genere una línea con ~k~ enteros, los índices de los ~k~ switches no utilizados, en orden creciente.

Entrada de ejemplo 1:

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

Saida de ejemplo 1:

2 
4 6

Entrada de ejemplo 2:

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

Saida de ejemplo 2:

0

Entrada de ejemplo 3:

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

Saida de ejemplo 3:

1
4