Sinh Vật Huyền Bí

Giáo sư Rubeus Hagrid đang nghiên cứu về sự đa dạng di truyền của các sinh vật huyền bí trong Rừng Cấm. Ông đã xây dựng một cây phả hệ di truyền gồm $N$ sinh vật, trong đó mỗi cạnh nối hai sinh vật có một trọng số biểu thị khoảng cách di truyền giữa chúng.

Hagrid muốn chọn ra đúng $K$ sinh vật để thành lập một đàn nuôi mới. Để đảm bảo sự đa dạng di truyền tối đa, ông muốn tổng khoảng cách di truyền giữa tất cả các cặp sinh vật được chọn là lớn nhất có thể.

Khoảng cách di truyền giữa hai sinh vật được tính bằng tổng trọng số các cạnh trên đường đi duy nhất giữa chúng trên cây phả hệ.

Hãy giúp Hagrid tìm tổng khoảng cách lớn nhất có thể.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $N$ và $K$ — số sinh vật và số sinh vật cần chọn.
• $N-1$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u$, $v$, $w$ — mô tả một cạnh nối sinh vật $u$ và $v$ với trọng số $w$.

Dữ liệu ra

In ra một số nguyên duy nhất — tổng khoảng cách di truyền lớn nhất giữa tất cả các cặp sinh vật được chọn.

Ràng buộc

• $2\le K\le N\le 2000$
• $1\le u,v\le N$, $u\ne v$
• $1\le w\le {10}^6$
• Các cạnh tạo thành một cây (đồ thị liên thông không có chu trình)
• Kết quả có thể vượt quá $2^{31}-1$

Ví dụ

Ghi chú

Trong ví dụ 1, cũng có thể chọn {1, 4, 5} cho cùng tổng 22: d(1,4) = 10, d(1,5) = 11, d(4,5) = 1. Tổng = 10 + 11 + 1 = 22.

Trong ví dụ 2, các sinh vật 3 và 5 có khoảng cách di truyền lớn nhất (7+6=13), và sinh vật 2 cũng cách xa cả hai, nên chọn bộ ba {2, 3, 5} cho tổng lớn nhất.