There was originally an undirected weighted graph $G$. Xiao Ai placed it into a kaleidoscope to observe it, which caused $G$ to appear as the union of $n$ copies generated by its rotation. Specifically, for every edge $(u, v, w) \in G$, all edges $((u+i) \bmod n + 1, (v+i) \bmod n + 1, w)$ are generated in $H$. The final graph $H$ is the result seen in the kaleidoscope.

Xiao Ai wants to know the sum of the weights of the minimum spanning tree of this graph. Please help her.

Input

The input contains multiple test cases. The first line contains a positive integer $T$, representing the number of test cases.

For each test case:

• The next line contains two positive integers $n, m$.
• The next $m$ lines each contain three positive integers $u, v, w$, representing an edge.

Output

Output $T$ lines, where the $i$-th line represents the answer to the $i$-th query.

Examples

Input 1

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

Output 1

4
3

Subtasks

For $100\%$ of the data, it is guaranteed that $1 \le T \le 100$; $1 \le n, w \le 10^9$; $\sum m \le 10^5$. It is guaranteed that a spanning tree exists.

Subtask 1 (30pts): $n, m \le 10$.

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

Subtask 3 (20pts): $w \le 2$.

Subtask 4 (30pts): No special restrictions.