Farmer John asiste a un curso nocturno de algoritmos en la universidad local y acaba de aprender sobre árboles de expansión mínima. Se da cuenta de que su granja podría ser más eficiente y quiere simplificar su distribución.

La granja es un grafo: los vértices son campos, y las aristas caminos entre ellos, cada uno con longitud. Farmer John observa que como máximo tres caminos comparten una longitud. FJ quiere quitar caminos para obtener un árbol, con una única ruta entre cada par de campos. Además quiere un árbol de expansión mínima, con la menor suma posible de longitudes.

Ayuda a Farmer John a calcular tanto esa suma como el número de árboles de expansión mínima distintos que puede crear.

Entrada

• Línea $1$: dos enteros $N$ y $M$, $1 \le N \le 40,000; 1 \le M \le 100,000$, números de vértices y aristas respectivamente. Los vértices se numeran $1\ldots N$.
• Líneas $2\ldots M+1$: tres enteros $a_{i}$, $b_{i}$, $n_{i}$, $1 \le a_{i}, b_{i} \le N; 1 \le n_{i} \le 1,000,000$, describen una arista de $a_{i}$ a $b_{i}$ de longitud $n_{i}$. Ninguna longitud $n_{i}$ aparece más de tres veces.

Salida

• Línea $1$: dos enteros, la longitud del árbol de expansión mínima y el número de estos árboles módulo $1,000,000,007$.

Ejemplos

Entrada 1

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

Salida 1

4 3

Nota

Elegir ambas aristas de longitud $1$ y cualquiera de longitud $2$ da un árbol de expansión mínima de longitud $4$.

Autor del problema: Nathan Pinsker, 2011