Farmer John segue un corso serale di algoritmi all'università locale e ha appena imparato gli alberi ricoprenti minimi. Si rende conto che la fattoria potrebbe essere più efficiente e vuole semplificarne la disposizione.

La fattoria è un grafo: i vertici sono campi e gli archi sentieri tra essi, ciascuno con una lunghezza. Farmer John osserva che al massimo tre sentieri condividono la stessa lunghezza. FJ vuole rimuoverne alcuni per ottenere un albero, con un unico percorso tra ogni coppia di campi. Vuole inoltre un albero ricoprente minimo, con la minima somma delle lunghezze degli archi.

Aiuta Farmer John a calcolare sia tale somma sia il numero di diversi alberi ricoprenti minimi che può creare.

Input

• Riga $1$: due interi $N$ e $M$, $1 \le N \le 40,000; 1 \le M \le 100,000$, numeri di vertici e archi rispettivamente. I vertici sono numerati $1\ldots N$.
• Righe $2\ldots M+1$: tre interi $a_{i}$, $b_{i}$, $n_{i}$, $1 \le a_{i}, b_{i} \le N; 1 \le n_{i} \le 1,000,000$, descrivono un arco da $a_{i}$ a $b_{i}$ di lunghezza $n_{i}$. Nessuna lunghezza $n_{i}$ compare più di tre volte.

Output

• Riga $1$: due interi, la lunghezza dell'albero ricoprente minimo e il numero di tali alberi modulo $1,000,000,007$.

Esempi

Input 1

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

Output 1

4 3

Nota

Scegliere entrambi gli archi di lunghezza $1$ e un qualsiasi arco di lunghezza $2$ dà un albero ricoprente minimo di lunghezza $4$.

Autore del problema: Nathan Pinsker, 2011