Đất nước JOI có \(N\) thành phố, được đánh số từ \(1\) đến \(N\). Các thành phố được nối với nhau bằng những con đường hai chiều tạo thành một cây. Nghĩa là giữa hai thành phố bất kỳ đều có thể đi lại theo các con đường, và đường đi đó là duy nhất. Khi đó, có \(N-1\) con đường.

Người ta quyết định chia các thành phố thành \(M\) vùng. Mỗi vùng phải chứa ít nhất một thành phố, và mỗi thành phố phải thuộc đúng một vùng. Ngoài ra, giữa hai thành phố bất kỳ trong cùng một vùng phải có thể đi lại theo các con đường mà không đi qua thành phố nào ngoài vùng đó.

Người ta muốn chia vùng sao cho giá trị lớn nhất trong các đường kính của các vùng, ký hiệu là \(d_{\max}\), nhỏ nhất có thể. Đường kính của một vùng là khoảng cách lớn nhất giữa hai thành phố thuộc vùng đó. Khoảng cách giữa hai thành phố là tổng độ dài các con đường trên đường đi nối chúng. Nếu một vùng chỉ chứa một thành phố thì đường kính của vùng đó được quy ước bằng \(0\).

Yêu cầu

Cho thông tin về các con đường và số vùng cần chia, hãy viết chương trình tính giá trị nhỏ nhất có thể của \(d_{\max}\).

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu tiên chứa hai số nguyên \(N\), \(M\), cách nhau bởi một dấu cách.
• Trong \(N-1\) dòng tiếp theo, mỗi dòng mô tả một con đường. Dòng thứ \(i\) trong số này chứa ba số nguyên \(A_i\), \(B_i\), \(C_i\), cách nhau bởi dấu cách, cho biết con đường thứ \(i\) nối hai thành phố \(A_i\), \(B_i\) và có độ dài \(C_i\).

Dữ liệu ra

In ra đầu ra chuẩn một số nguyên là giá trị nhỏ nhất có thể của \(d_{\max}\).

Ràng buộc

• Giới hạn trong kỳ thi gốc: thời gian \(1\) giây, bộ nhớ \(64\) MB.

• Trong kỳ thi gốc, kích thước ngăn xếp (stack) chỉ bị giới hạn bởi giới hạn bộ nhớ của bài, không có giới hạn riêng nhỏ hơn.

• \(2\le N\le30\,000\): số thành phố.

• \(2\le M\le N\): số vùng.
• \(1\le A_i<B_i\le N\) với \(1\le i\le N-1\): hai thành phố được nối bởi con đường thứ \(i\).
• \(1\le C_i\le100\) với \(1\le i\le N-1\): độ dài con đường thứ \(i\).

Phân nhóm

Bài này có tổng cộng \(100\) điểm, gồm \(10\) bộ dữ liệu, mỗi bộ \(10\) điểm.

• Nhóm test trị giá \(20\) điểm: \(M=2\) và \(N\le1\,000\).
• Nhóm test trị giá \(40\) điểm: \(M=2\).

Ví dụ

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

3

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

2