Tô màu cây

Cho một cây có trọng số gồm $n$ đỉnh. Cạnh thứ $i$ nối hai đỉnh $u_i$ và $v_i$, có trọng số $w_i$.

Một cách tô màu $k$ của cây là việc gán cho mỗi đỉnh đúng $k$ màu, sao cho mỗi màu được dùng ở nhiều nhất hai đỉnh. Bạn có vô hạn màu để sử dụng.

Một cạnh được gọi là bão hòa nếu hai đầu mút của nó có chung ít nhất một màu (tồn tại một màu được gán cho cả hai đỉnh).

Giá trị của một cách tô màu $k$ là tổng trọng số của các cạnh bão hòa.

Hãy tính giá trị lớn nhất có thể của một cách tô màu $k$ của cây đã cho.

Bạn phải trả lời $q$ truy vấn độc lập.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $q$, số lượng truy vấn.
• Với mỗi truy vấn:
  • Dòng đầu chứa hai số nguyên $n$ và $k$, số đỉnh của cây và số màu gán cho mỗi đỉnh.
  • $n-1$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u_i$, $v_i$, $w_i$, mô tả một cạnh.

Dữ liệu đảm bảo các cạnh tạo thành một cây.

Dữ liệu ra

Với mỗi truy vấn, in ra một số nguyên là giá trị lớn nhất của cách tô màu $k$.

Ràng buộc

• $1\le q\le 5·{10}^5$
• $1\le n,k\le 5·{10}^5$
• $1\le u_i,v_i\le n$, $u_i\ne v_i$
• $1\le w_i\le {10}^5$
• Tổng của tất cả $n$ trên mọi truy vấn không vượt quá $5·{10}^5$.

Ví dụ