Sai Heidi đi xa hơn

Heidi có $n$ người bạn được đánh số từ $0$ đến $n-1$. Mạng lưới quan hệ bạn bè tạo thành một cây: có đúng $n-1$ cặp bạn bè trực tiếp, mỗi cặp $(u,v)$ có một chi phí di chuyển $c$.

Heidi bắt đầu tại bạn số $0$ và sẽ bị "đẩy" qua lại giữa các bạn theo một chuỗi di chuyển nào đó dọc các cạnh của cây. Trong phiên bản này, không có bạn nào bị thăm quá $k$ lần (lần xuất hiện đầu tiên tại bạn $0$ cũng được tính).

Khi đi giữa hai người bạn $u$ và $v$, Heidi phải mua vé một lần với chi phí $c(u,v)$; sau đó cô có thể đi lại giữa cặp này tự do trong cả ngày. Nói cách khác, mỗi cạnh chỉ bị tính chi phí một lần duy nhất, không phụ thuộc số lần đi qua.

Hãy tính số tiền lớn nhất Heidi có thể phải trả trong trường hợp tệ nhất — tức là tổng chi phí lớn nhất của tập các cạnh được sử dụng, lấy max trên mọi chuỗi di chuyển hợp lệ thoả mãn ràng buộc số lần thăm.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $k$.
• $n-1$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u$, $v$, $c$ — mô tả một cạnh giữa $u$ và $v$ với chi phí $c$.

Dữ liệu ra

In ra một số nguyên — tổng chi phí lớn nhất trong trường hợp xấu nhất.

Ràng buộc

• $1\le n\le {10}^5$
• $1\le k\le {10}^5$
• $0\le u,v\le n-1$
• $1\le c\le {10}^4$ (một số test sinh có thể chứa $c=0$)
• Đồ thị đầu vào luôn là một cây.

Ví dụ