Farmer John frequenta um curso noturno de algoritmos na universidade local e acaba de aprender sobre árvores geradoras mínimas. Percebe que a fazenda poderia ser mais eficiente e quer simplificar sua disposição.

A fazenda é um grafo: vértices representam campos e arestas caminhos entre eles, cada qual com um comprimento. Farmer John observa que no máximo três caminhos têm o mesmo comprimento. FJ quer remover caminhos para obter uma árvore, com uma única rota entre cada par de campos. Além disso, quer uma árvore geradora mínima, cuja soma dos comprimentos seja a menor possível.

Ajude Farmer John a calcular tanto essa soma como o número de árvores geradoras mínimas diferentes que pode criar.

Entrada

• Linha $1$: dois inteiros $N$ e $M$, $1 \le N \le 40,000; 1 \le M \le 100,000$, números de vértices e arestas respectivamente. Os vértices são numerados $1\ldots N$.
• Linhas $2\ldots M+1$: três inteiros $a_{i}$, $b_{i}$, $n_{i}$, $1 \le a_{i}, b_{i} \le N; 1 \le n_{i} \le 1,000,000$, descrevem uma aresta de $a_{i}$ a $b_{i}$ de comprimento $n_{i}$. Nenhum comprimento $n_{i}$ aparece mais de três vezes.

Saída

• Linha $1$: dois inteiros, o comprimento da árvore geradora mínima e o número dessas árvores módulo $1,000,000,007$.

Exemplos

Entrada 1

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

Saída 1

4 3

Nota

Escolher ambas as arestas de comprimento $1$ e qualquer aresta de comprimento $2$ dá uma árvore geradora mínima de comprimento $4$.

Autor do problema: Nathan Pinsker, 2011