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