Мир представляет собой связный граф, состоящий из $n$ городов и $m$ транспортных маршрутов. Каждый маршрут имеет свой вес. Вес связного подграфа $w(s)$ определяется как результат операции «исключающее ИЛИ» (XOR) между весом его минимального остовного дерева и весом его максимального остовного дерева.

Примечание:

• $w(s)$ определено только для связных подграфов $(s, E_s)$ графа $G$;
• Для связного подграфа $(s, E_s)$, где $s$ — множество вершин, а $E_s = \{(u, v) \in s\}$ — множество всех рёбер, оба конца которых принадлежат $s$, «связность» означает, что любые две вершины в $s$ могут быть соединены путём, состоящим из рёбер множества $E_s$.

Изначально вы можете выбрать один город, с которого начнется развитие. Предположим, что текущее множество зараженных городов — $S$, а следующее множество городов после расширения — $T$ (при условии, что $S \subset T$ и $T$ связно). Тогда затраты очков ДНК на этот шаг составляют $(|T| - |S|) \times w(T)$.

Найдите план заражения, то есть последовательность множеств $S_1 \subset S_2 \subset \dots \subset S_k$, где $S_1$ содержит только один город, $S_k$ содержит все города, каждое множество в последовательности связно, а суммарные затраты очков ДНК на расширение минимальны.

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

Первая строка содержит два целых положительных числа $n$ и $m$, обозначающих количество городов и количество дорог соответственно.

Следующие $m$ строк содержат по 3 целых положительных числа $u, v, w$, описывающих транспортный маршрут.

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

Выведите одно целое положительное число — минимальную стоимость в очках ДНК.

Примеры

Пример 1

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

3 3
1 2 1
2 3 2
1 3 3

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

6

Пример 2

См. приложенные файлы.

Пример 3

См. приложенные файлы.

Подзадачи

Для 100% данных: $1 \le n \le 20$, $1 \le m \le 100$, $1 \le w \le 10000$, граф гарантированно связен.

• Подзадача 1 (20 баллов): $n \le 3, m \le 10$
• Подзадача 2 (10 баллов): $n \le 4, m \le 10$
• Подзадача 3 (10 баллов): $n \le 5, m \le 10$
• Подзадача 4 (20 баллов): $n \le 10, m \le 100$
• Подзадача 5 (20 баллов): $n \le 16, m \le 100$
• Подзадача 6 (20 баллов): $n \le 20, m \le 100$