In Search of Gold

Problem Description

Sunset got a map about an abandoned gold mine in the border town. The map shows that the gold mine consists of $n$ rooms connected by $n-1$ bidirectional tunnels, forming a tree structure. The map is so strange that on the $i$-th tunnel, there are two numbers $a_i$ and $b_i$. The only thing Sunset knows is that there are exactly $k$ tunnels whose lengths are taken from $a$ while the lengths of other $n-k-1$ tunnels are taken from $b$. Tomorrow Sunset will explore that gold mine. He is afraid of getting lost in the gold mine, so can you please tell him the diameter of the gold mine if he is lucky enough? In other words, please calculate the minimum possible length of the diameter from the information Sunset has.

Input

The first line of the input contains a single integer $T$ ($1 \leq T \leq 10\,000$), the number of test cases. For each case, the first line of the input contains two integers $n$ and $k$ ($2 \leq n \leq 20\,000$, $0\leq k\leq n-1$, $k\leq 20$), denoting the number of rooms and the parameter $k$. Each of the following $n-1$ lines contains four integers $u_i,v_i,a_i$ and $b_i$ ($1\leq u_i,v_i\leq n$, $u_i\neq v_i$, $1\leq a_i,b_i\leq 10^9$), denoting an bidirectional tunnel between the $u_i$-th room and the $v_i$-th room, the length of which is either $a_i$ or $b_i$. It is guaranteed that the sum of all $n$ is at most $200\,000$.

Output

For each test case, output a single line containing an integer, the minimum possible length of the diameter.

Sample Input

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

Sample Output

6

Source

2020 Multi-University Training Contest 2