Camino al cole
Lucas va todos los días en bici al cole. Como le cuesta una barbaridad levantarse por las mañanas, siempre lleva prisa y tiene que ir por el camino más corto. Pero le aburre ir siempre por el mismo camino, por lo que va alternando, eso sí, recorriendo siempre la misma distancia mínima, para no llegar tarde. Como es un poco temerario, no respeta el sentido de circulación de las calles por lo que es capaz de recorrer cualquiera de ellas en ambos sentidos. Ahora se pregunta de cuántas formas distintas puede ir de su casa al colegio sin recorrer ni un centímetro de más.
Por ejemplo, si el siguiente esquema representara el pueblo de Lucas, con 7 intersecciones y 10 calles, donde junto a cada calle aparece su longitud, Lucas viviera en la intersección número 1 y su colegio se encontrara en la intersección 7, entonces Lucas podría ir al colegio de 4 formas distintas recorriendo una distancia de 40 (1 → 2 → 4 → 5 → 7, 1 → 2 → 4 → 7, 1 → 3 → 4 → 7 y 1 → 3 → 4 → 5 → 7).
Entrada
La entrada está compuesta por diversos casos de prueba, ocupando cada uno de ellos varias líneas.
En la primera línea aparece el número N (entre 1 y 10.000) de intersecciones en el pueblo de Lucas, y en la segunda línea aparece el número C (entre 0 y 100.000) de calles (entre intersecciones). A continuación, aparece una línea por cada calle con tres enteros, que indican los números de las intersecciones que une la calle (números entre 1 y N) y su longitud (un valor entre 1 y 100.000). Nunca hay una calle que conecte una intersección consigo misma, ni dos calles que conecten el mismo par de intersecciones.
La casa de Lucas siempre se encuentra en la intersección número 1 y su colegio está situado en la intersección número N.
Salida
Para cada caso de prueba se escribirá una línea con el número de formas distintas de ir desde la casa de Lucas al colegio recorriendo la mínima distancia posible. Este número siempre será menor que 231.
Entrada de ejemplo
7 10 1 2 5 1 3 7 2 4 10 3 4 8 2 5 30 4 5 12 4 7 25 4 6 11 5 7 13 6 7 30
Salida de ejemplo
4