Farmer John uczęszcza na wieczorowy kurs algorytmów na miejscowym uniwersytecie i właśnie poznał minimalne drzewa rozpinające. Dostrzega, że układ farmy mógłby być wydajniejszy, i chce go uprościć.

Farma jest grafem: wierzchołki to pola, krawędzie to ścieżki między nimi, każda o pewnej długości. Farmer John zauważa, że najwyżej trzy ścieżki mają tę samą długość. FJ chce usunąć część ścieżek, tworząc drzewo, czyli jedyną drogę między każdą parą pól. Ma to być minimalne drzewo rozpinające, z najmniejszą sumą długości krawędzi.

Pomóż Farmer John obliczyć zarówno tę sumę, jak i liczbę różnych minimalnych drzew rozpinających, które może utworzyć.

Wejście

• Wiersz $1$: dwie liczby całkowite $N$ i $M$, $1 \le N \le 40,000; 1 \le M \le 100,000$, liczby wierzchołków i krawędzi odpowiednio. Wierzchołki są numerowane $1\ldots N$.
• Wiersze $2\ldots M+1$: trzy liczby całkowite $a_{i}$, $b_{i}$, $n_{i}$, $1 \le a_{i}, b_{i} \le N; 1 \le n_{i} \le 1,000,000$, opisują krawędź z $a_{i}$ do $b_{i}$ długości $n_{i}$. Żadna długość $n_{i}$ nie występuje więcej niż trzy razy.

Wyjście

• Wiersz $1$: dwie liczby całkowite — długość minimalnego drzewa rozpinającego i liczba takich drzew modulo $1,000,000,007$.

Przykład

Wejście 1

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

Wyjście 1

4 3

Uwagi

Wybranie obu krawędzi długości $1$ i dowolnej krawędzi długości $2$ daje minimalne drzewo rozpinające długości $4$.

Autor zadania: Nathan Pinsker, 2011