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}\)