Дороги

В стране Олимпии есть N городов и M дорог. Дороги имеют различные длины, каждая из которых является степенью двойки от 2^0 до 2^(M-1). Ваша задача — найти сумму всех кратчайших расстояний между парами городов и вывести её в двоичной записи.

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

Первая строка содержит два числа: N и M.

Следующие M строк описывают дороги. Каждая дорога задается тремя числами A, B и C, что означает наличие двунаправленной дороги между городами A и B длиной 2^C. Здесь 1 ≤ A, B ≤ N, 0 ≤ C ≤ M - 1.

Все длины дорог уникальны. Гарантируется, что граф связен и корректно задан.

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

Выведите сумму кратчайших расстояний между каждой парой городов в двоичной записи. Учтите, что ответ может быть очень большим.

Ограничения

• 20 баллов: 1 ≤ N, M ≤ 20

• 40 баллов: 1 ≤ N, M ≤ 10^3

• 40 баллов: 1 ≤ N, M ≤ 10^5

Примеры

Оценивание

Для лучшего понимания задачи нарисуйте граф.

Пример расстояний:

• Расстояние от 1 до 2: 2^0

• Расстояние от 1 до 3: 2^0 + 2^2

• Расстояние от 1 до 4: 2^0 + 2^2 + 2^1

• Расстояние от 2 до 3: 2^2

• Расстояние от 2 до 4: 2^2 + 2^1

• Расстояние от 3 до 4: 2^1

Итоговая сумма: 3 * 2^0 + 3 * 2^1 + 4 * 2^2 = 2^0 + 2^3 + 2^4 = 11001[2]