Dana jest nieskierowany graf ważony $G$. Xiao Ai umieściła go w kalejdoskopie, co sprawia, że $G$ wygląda jak suma $n$ kopii powstałych w wyniku rotacji. Dokładniej, dla każdej krawędzi $(u, v, w) \in G$, w grafie $H$ generowane są wszystkie krawędzie postaci $((u+i) \bmod n + 1, (v+i) \bmod n + 1, w)$ dla $0 \le i < n$. Ostateczny graf $H$ jest wynikiem widzianym w kalejdoskopie.

Xiao Ai chce poznać sumę wag minimalnego drzewa rozpinającego tego grafu. Pomóż jej.

Wejście

Zadanie zawiera wiele zestawów danych. Pierwsza linia zawiera liczbę całkowitą dodatnią $T$ oznaczającą liczbę zestawów danych.

Dla każdego zestawu danych:

• W kolejnej linii znajdują się dwie liczby całkowite dodatnie $n, m$.
• Następnie $m$ linii, z których każda zawiera trzy liczby całkowite dodatnie $u, v, w$, opisujące krawędź.

Wyjście

Wypisz $T$ linii, gdzie $i$-ta linia zawiera odpowiedź dla $i$-tego zestawu danych.

Przykład

Przykład 1

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

Wyjście 1

4
3

Podzadania

Dla $100\%$ danych spełnione są warunki: $1 \le T \le 100$; $1 \le n, w \le 10^9$; $\sum m \le 10^5$. Gwarantuje się, że drzewo rozpinające istnieje.

Podzadanie 1 (30 pkt): $n, m \le 10$.

Podzadanie 2 (20 pkt): $\sum n \cdot m \le 10^5$.

Podzadanie 3 (20 pkt): $w \le 2$.

Podzadanie 4 (30 pkt): Brak dodatkowych ograniczeń.