You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

Gov. 正在监管 Alice 经营的区域连锁市场。最初， Alice 只有一个市场，这个市场覆盖了 Gov. 管理下的 n 个区域。

这 n 个区域之间两两有且仅有一条路径可相互抵达，同时每一条路径都有一定的权值。

随着 Alice 的营业额日益增加， Gov. 意识到这样一个包括了所有区域的大型市场是垄断的，因此决定将这个大型市场划分为 k 个不相互连通的小型市场。

为了更好地描述一个市场的垄断程度， Gov. 制定了标准，规定一个市场的危险度为它在图论意义上的直径，也就是 $\max_{u,v\in S}{dis(u,v)}$，其中 S 为属于市场的区域集合， dis(u, v) 为 u, v 两个区域的距离。

现在 Gov. 将给你这 n 个区域的相关信息，并希望在 Alice 的大型市场被分为 k 个小型市场的限制下，这 k 个市场危险度的最大值最小。

Format

Input

第一行两个正整数 n, k。

接下来 n - 1 行每行三个正整数 ui, vi, wi 表示 ui, vi 两个区域之间存在一条长度为 wi 的边。

Output

一个正整数 ans 表示答案

Samples

5 4
1 2 7
2 3 4
3 4 9
4 5 5

4

15 8
12 14 8
7 11 7
4 7 5
13 1 3
1 5 8
3 9 2
4 8 6
1 4 6
1 6 8
12 1 8
6 10 7
1 3 4
8 15 7
1 2 4

8

Limitation

n ≤ 2000

k ≤ 2000

wi, ans ≤ 4000