Toll charges
/

## Algorithms, DFS, Dynamic Programming, Trees

Problem
Editorial
Analytics

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}$

SAMPLE INPUT
4
4 1
1 2 10 1000
2 3 10 1000
2 4 10 1000
2 0
1 2 4 5
4 0
1 2 1 1
3 1 5 5
3 4 1 10
4 1
1 2 1 1
3 1 5 5
3 4 1 10

SAMPLE OUTPUT
40
4
14
4

Explanation

First Sample: Here clearly using roads to move from city 2 to 1, or from city 3 to 2 or from city 4 to 2 is very costly (1000). Here remove the toll charge of road connecting cities 2 and 4 (now friend at city 4 can come to city 2 without paying any toll charge). Now it is optimal for all friends to meet at city 3. Toll charge paid to move from city 1 to city 3 is 20, from city 2 to city 3 is 10 and from city 4 to city 3 is 10. So total toll charge is 40.

Second Sample: Here friend from city 1 move to city 2 and pay a toll charge of 4.

Third Sample: Here it is optimal to meet at city 4. Toll charge paid to move from city 1 to city 4 is 6, from city 2 to city 4 is 7 and from city 3 to city 4 is 1. So total toll charge is 14.

Time Limit: 3.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

## This Problem was Asked in

Initializing Code Editor...