Фермер Джон изучает программирование на вечерних курсах при местном университете и сейчас проходит тему "минимальное остовное дерево". Он осознал, что проект его фермы не оптимален, и хочет его улучшить.
Ферма сейчас организована в виде графа, вершины которого представляют поля, а ребра представляют дорожки между этим полями, с каждой ассоциирована ее длина.
ФД заметил, что для каждой длины имеется не более трех дорожек, имеющих такую длину. ФД хочет удалить некоторые из дорожек на своей ферме так, чтобы получилось дерево - то есть, чтобы существовал единственный путь между любыми двумя полями. Более того, Фд хочет, чтобы это было минимальное остовное дерево, то есть дерево, которое имеет минимально возможную сумму длин всех дорожек.
Помогите ФД вычислить не только сумму длин всех дорожек в минимальном остовном дереве, но также количество различных возможных минимальных остовных деревьев, которые он может создать.
PROBLEM NAME: simplify
Формат входных данных
* Строка 1: Два целых числа N и M (1 <= N <= 40,000; 1 <= M <= 100,000), представляющих количество вершин и ребер соответственно. Вершины пронумерованы от 1 до N.
* Строки 2..M+1: Три целых числа ai, bi ni (1 <= ai, bi <= N; 1 <= ni <= 1,000,000) представляющих ребро от вершины ai до bi длиной ni. Никакое ребро с длиной ni не встретиться более трех раз.
Формат выходных данных
* Строка 1: Два целых числа, представляющих длину минимального остовного дерева и количество минимальных остовных деревьев (по модулю 1,000,000,007)
Примечание
Выбрав оба ребра с длиной 1 и любое ребро с длиной 2 мы получим минимальное остовное дерево с длиной 4.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 5
1 2 1
3 4 1
1 3 2
1 4 2
2 3 2
|
4 3
|