Изначально был задан неориентированный взвешенный граф $G$. Сяо Ай поместила его в калейдоскоп, из-за чего $G$ стал выглядеть как объединение $n$ своих копий, полученных путем вращения. Конкретнее, для каждого ребра $(u,v,w)\in G$ в графе $H$ создается множество ребер $((u+i)\bmod n + 1, (v+i)\bmod n + 1, w)$ для всех $0 \le i < n$. Итоговый граф $H$ — это результат, наблюдаемый в калейдоскопе.

Сяо Ай хочет узнать сумму весов ребер минимального остовного дерева этого графа. Помогите ей.

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

Задача содержит несколько наборов входных данных. В первой строке задано целое положительное число $T$ — количество наборов данных.

Для каждого набора данных:

• В следующей строке заданы два целых положительных числа $n, m$.
• В следующих $m$ строках заданы по три целых положительных числа $u, v, w$, описывающих ребро.

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

Выведите $T$ строк, где $i$-я строка содержит ответ для $i$-го набора данных.

Примеры

Пример 1

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

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

4
3

Подзадачи

Для $100\%$ данных гарантируется, что $1\le T\le 100; 1\le n, w\le 10^9; \sum m\le 10^5$. Гарантируется, что остовное дерево существует.

Подзадача 1 (30 баллов): $n, m\le 10$.

Подзадача 2 (20 баллов): $\sum n\cdot m\le 10^5$.

Подзадача 3 (20 баллов): $w\le 2$.

Подзадача 4 (30 баллов): без дополнительных ограничений.