Vas a viajar de Syrjälä a Lehmälä en avión. Quieres encontrar las respuestas a las siguientes preguntas:

• ¿Cuál es el precio mínimo de esta ruta?
• ¿Cuántas rutas con precio mínimo existen? (módulo ~10^9+7~)
• ¿Cuál es el número mínimo de vuelos en una ruta con precio mínimo?
• ¿Cuál es el número máximo de vuelos en una ruta con precio mínimo?

Entrada

La primera línea de entrada contiene dos números enteros, ~n~ y ~m~: el número de ciudades y el número de vuelos. Las ciudades están numeradas del ~1~ al ~n~. La ciudad ~1~ es Syrjälä y la ciudad ~n~ es Lehmälä.

A continuación, hay ~m~ líneas que describen los vuelos. Cada línea contiene tres números enteros, ~a, b~ y ~c~: hay un vuelo de la ciudad ~a~ a la ciudad ~b~ con precio ~c~. Todos los vuelos son de ida. Puede asumir que existe una ruta de Syrjälä a Lehmälä.

Salida

Imprima cuatro números enteros según el enunciado del problema.

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

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

Ejemplo de Salida

5 2 1 2