Bogdan ha pasado todo el verano arreglando su bici y ahora que comienzan las clases, necesitará ir a la universidad todos los días, y ha decidido hacerlo en bici. Para no aburrirse, Bogdan ha decidido que cada día tomará un camino diferente para llegar desde su casa hasta la universidad. Como los exámenes empezarán pronto, solo considerará aquellos caminos que minimicen la distancia total recorrida. Tu misión es ayudar a contar de cuántas maneras es posible llegar desde la casa de Bogdan a la universidad recorriendo la menor distancia posible.
Entrada
La primera línea contiene el número de casos de prueba (\(t \le 20\)).
La primera línea de cada caso de prueba contiene el número de intersecciones entre calles (\(1 \le n \le 10^5\)), y el número de calles \(m\) (\(1 \le m \le 10^5\)), respectivamente.
Después, siguen \(m\) líneas, cada una describiendo una calle. La descripción de una calle consta de las dos intersecciones que se unen (\(1 \le u, v \le n\)) y la distancia de la calle (\(1 \le c \le 10^4\)). Las calles son bidireccionales.
Salida
Por cada caso de prueba, se debe escribir una línea con el número válido de maneras diferentes para llegar desde la casa de Bogdan (intersección 1) a la universidad (intersección \(n\)) recorriendo la mínima distancia posible.