There are $N$ friends living in $N$ different cities. These cities are connected by $N-1$ roads such that it is possible to reach any city from another city. Each road connects two different cities $x$ and $y$. The toll charge of using these roads to go from city $x$ to city $y$ can be different from the toll charge of using these roads to go from city $y$ to city $x$.

If all $N$ friends want to meet you, then they can meet in any city. One of your friends can remove toll charges of up to $K$ roads. Determine the minimum total toll charge your friends have to pay. Each friend is coming in his own vehicle, so everyone is paying a separate toll charge.

Note: No one pays the toll charge for a road for which toll charges were removed.

Input format

• First line: A single integer $T$ denoting the number of test cases
• For each test case:
  • First line: Two integers $N$ and $K$ denoting the number of cities and the maximum number of roads on which toll charges are removed respectively
  • Next $N-1$ lines: Four integers $x$, $y$, $a$, and $b$
    Note: Here, cities $x$ and $y$ are connected by some road. The toll charge on the road that is used to travel from city $x$ to city $y$ is $a$ and the toll charge when this road is used to travel from city $y$ to city $x$ is $b$.

Output format

For each test case, print the minimum total toll charge that must be paid to meet in a city.

Constraints

$1\le T \le 10$

$1\le N \le 10^{4}$

$0\le K \le N-1$

$1 \le x, y \le N,\ 1 \le a, b \le 10^{9}$