Арыки Алайской долины
Фермеры Алайской долины хотят соединить n полей системой арыков. Инженеры подготовили m возможных каналов: канал i соединяет поля a[i] и b[i] и стоит w[i] тысяч сомов. Вода по каналу течёт в обе стороны, между двумя полями может быть несколько вариантов канала.
Система арыков — это набор каналов, по которому вода может добраться от любого поля до любого другого, причём из всех таких наборов выбирается самый дешёвый. Комиссия хочет знать, сколько вообще существует различных самых дешёвых систем: два набора различны, если какой-то канал входит ровно в один из них.
Входные данные
В первой строке — два целых числа n и m (2 ≤ n ≤ 400, 1 ≤ m ≤ 10⁵). В каждой из следующих m строк — три целых числа a[i], b[i], w[i] (1 ≤ a[i], b[i] ≤ n, a[i] ≠ b[i], 1 ≤ w[i] ≤ 10⁹).
Выходные данные
Если соединить все поля нельзя, выведите -1. Иначе выведите два числа: наименьшую стоимость системы и количество самых дешёвых систем по модулю 10⁹ + 7.
Пример 1
Вход:
4 5
1 2 1
2 3 1
1 3 1
3 4 2
2 4 3
Выход:
4 3
Пояснение
На рисунке — пример. Самая дешёвая система стоит 4: в неё всегда входит канал 3–4 стоимостью 2, а из треугольника 1–2–3 с каналами стоимостью 1 можно взять любые два канала. Получается 3 системы.
Система оценивания
Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 20 % тестов m ≤ 16.
Подсказка
Матричная теорема о деревьях (Кирхгоф): число остовных деревьев мультиграфа равно любому главному минору порядка n − 1 его матрицы Кирхгофа (степени на диагонали, минус число рёбер между вершинами вне диагонали).
Комментарии