Farmer John besucht einen abendlichen Algorithmuskurs an der örtlichen Universität und hat gerade minimale Spannbäume kennengelernt. Er erkennt, dass seine Farm effizienter gestaltet werden könnte, und möchte ihren Aufbau vereinfachen.

Die Farm ist ein Graph: Knoten sind Felder, Kanten sind Wege dazwischen mit jeweils einer Länge. Farmer John bemerkt, dass höchstens drei Wege dieselbe Länge haben. FJ möchte Wege entfernen, um einen Baum zu erhalten, also genau eine Route zwischen jedem Feldpaar. Es soll zudem ein minimaler Spannbaum mit kleinstmöglicher Summe der Kantenlängen sein.

Hilf Farmer John, sowohl diese Summe als auch die Anzahl verschiedener minimaler Spannbäume zu berechnen, die er bilden kann.

Eingabe

• Zeile $1$: zwei ganze Zahlen $N$ und $M$, $1 \le N \le 40,000; 1 \le M \le 100,000$, die Knoten- bzw. Kantenzahl. Die Knoten sind mit $1\ldots N$ nummeriert.
• Zeilen $2\ldots M+1$: drei ganze Zahlen $a_{i}$, $b_{i}$, $n_{i}$, $1 \le a_{i}, b_{i} \le N; 1 \le n_{i} \le 1,000,000$, beschreiben eine Kante von $a_{i}$ nach $b_{i}$ mit Länge $n_{i}$. Keine Länge $n_{i}$ erscheint mehr als dreimal.

Ausgabe

• Zeile $1$: zwei ganze Zahlen, die Länge des minimalen Spannbaums und die Anzahl solcher Bäume modulo $1,000,000,007$.

Beispiele

Eingabe 1

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

Ausgabe 1

4 3

Hinweis

Beide Kanten der Länge $1$ und eine beliebige Kante der Länge $2$ ergeben einen minimalen Spannbaum der Länge $4$.

Aufgabenautor: Nathan Pinsker, 2011