Farmer John suit un cours du soir d'algorithmique à l'université locale et vient de découvrir les arbres couvrants de poids minimum. Il réalise que sa ferme pourrait être mieux organisée et souhaite en simplifier le plan.

La ferme est un graphe : les sommets sont les champs, les arêtes les chemins entre eux, chacun muni d'une longueur. Farmer John remarque que chaque longueur apparaît pour au plus trois chemins. FJ veut supprimer certains chemins pour obtenir un arbre, avec un trajet unique entre chaque paire de champs. Il veut en outre un arbre couvrant minimum, dont la somme des longueurs soit minimale.

Aidez Farmer John à calculer cette somme et le nombre d'arbres couvrants minimums différents qu'il peut créer.

Entrée

• Ligne $1$ : deux entiers $N$ et $M$, $1 \le N \le 40,000; 1 \le M \le 100,000$, donnant respectivement les nombres de sommets et d'arêtes. Les sommets sont numérotés $1\ldots N$.
• Lignes $2\ldots M+1$ : trois entiers $a_{i}$, $b_{i}$, $n_{i}$, $1 \le a_{i}, b_{i} \le N; 1 \le n_{i} \le 1,000,000$, donnent une arête de $a_{i}$ à $b_{i}$ de longueur $n_{i}$. Aucune longueur $n_{i}$ n'apparaît plus de trois fois.

Sortie

• Ligne $1$ : deux entiers, la longueur de l'arbre couvrant minimum et le nombre de ces arbres modulo $1,000,000,007$.

Exemples

Entrée 1

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

Sortie 1

4 3

Remarque

Choisir les deux arêtes de longueur $1$ et n'importe quelle arête de longueur $2$ donne un arbre couvrant minimum de longueur $4$.

Auteur du problème : Nathan Pinsker, 2011