Farmer John посещает вечерний курс алгоритмов в местном университете и только что изучил минимальные остовные деревья. Он понял, что ферма устроена не столь эффективно, как могла бы, и хочет упростить её план.

Ферма — граф: вершины представляют поля, рёбра — дороги между ними, каждая с длиной. Farmer John замечает, что каждая длина встречается не более чем у трёх дорог. FJ хочет удалить часть дорог, получив дерево, то есть единственный путь между любыми двумя полями. Более того, это должно быть минимальное остовное дерево с наименьшей суммой длин рёбер.

Помогите Farmer John вычислить и сумму длин минимального остовного дерева, и число различных таких деревьев, которые можно создать.

Входные данные

• Строка $1$: два целых числа $N$ и $M$, $1 \le N \le 40,000; 1 \le M \le 100,000$, числа вершин и рёбер соответственно. Вершины имеют номера $1\ldots N$.
• Строки $2\ldots M+1$: три целых числа $a_{i}$, $b_{i}$, $n_{i}$, $1 \le a_{i}, b_{i} \le N; 1 \le n_{i} \le 1,000,000$, задают ребро из $a_{i}$ в $b_{i}$ длины $n_{i}$. Каждая длина $n_{i}$ встречается не более трёх раз.

Выходные данные

• Строка $1$: два целых числа — длина минимального остовного дерева и число таких деревьев по модулю $1,000,000,007$.

Примеры

Входные данные 1

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

Выходные данные 1

4 3

Примечание

Оба ребра длины $1$ и любое ребро длины $2$ дают минимальное остовное дерево длины $4$.

Автор задачи: Nathan Pinsker, 2011