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