There are $N$ cities in a country. There are $M$ roads with parameters $(L,\ R,\ W)$ denoting cities $L$ and $R$ that are connected and a road that was built between them for $W$$. Note that the roads are bidirectional in nature. 

Now, a new policy is introduced to act that states the following:

• Let $X$ be the maximum number of roads between any pair of cities. All the pairs of cities that have fewer than $X$ roads between them will be reconstructed and the cost of building the roads will be the same as before.

Determine the amount of money that will be required for implementing the new policy?

Input format

• The first line contains an integer $T$ denoting the number of test cases.
• The first line of each test case contains two space-separated integers $N$ and $M$ denoting the number of cities and number of roads.
• Next $M$ lines contain three space-separated integers representing $(L,\ R,\ W)$.

Output format

For each test case, print a single line denoting the fund required according to the new policy. 

Constraints

$1 \leq T \leq 20000$

$1 \leq N,M \leq 200000$

$1 \leq L,R \leq N$

$1 \leq W \leq 10^9$

The sum of $N$ and $M$ over all test case do not exceed 200000.