索尼娅非常喜欢冰淇淋。她甚至在编程比赛期间也吃它。这就是为什么这个女孩决定开一家自己的冰淇淋店。
索尼娅住在一座有 $$$n$$$ 路口的城市,路口之间有 $$$n-1$$$ 街道。所有街道都是双向的,连接两个路口。可以使用一条或多条街道从任何路口前往任何其他路口。市政厅只允许在路口开设商店。这个女孩不能在街道中间开商店。
Sonya has exactly $$$k$$$ friends whom she can trust.如果她开一家商店,她的一个朋友必须在那里工作,并且不允许任何人不付钱就吃冰淇淋。 Since Sonya does not want to skip an important competition, she will not work in shops personally.
Sonya 希望她所有的冰淇淋店形成一条长度为 $$$r$$$ ($$$1 \le r \le k$$$) 的简单路径,即位于不同的路口 $$$f_1, f_2, \dots, f_r$$$ 并且每个冰淇淋店在 $$$f_i$$$ 和 $$$f_{i+1}$$$ 之间有一条街道$$$i$$$ 从 $$$1$$$ 到 $$$r-1$$$。
The girl takes care of potential buyers, so she also wants to minimize the maximum distance between the junctions to the nearest ice cream shop.两个路口 $$$a$$$ 和 $$$b$$$ 之间的距离等于从路口 $$$a$$$ 到路口 $$$b$$$ 所需经过的所有街道长度的总和。所以索尼娅想要最小化
$$$$$$\max_{a} \min_{1 \le i \le r} d_{a,f_i}$$$$$$
其中 $$$a$$$ 取所有可能的 $$$n$$$ 路口的值,$$$f_i$$$ — 第 $$$i$$$ 个 Sonya 商店所在的路口,$$$d_{x,y}$$$ — 路口 $$$x$$$ 和 $$$y$$$ 之间的距离。
Sonya is not sure that she can find the optimal shops locations, that is why she is asking you to help her to open not more than $$$k$$$ shops that will form a simple path and the maximum distance between any junction and the nearest shop would be minimal.
输入
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1\leq k\leq n\leq 10^5$$$) — the number of junctions and friends respectively.
Each of the next $$$n-1$$$ lines contains three integers $$$u_i$$$, $$$v_i$$$, and $$$d_i$$$ ($$$1\leq u_i, v_i\leq n$$$, $$$v_i\neq u_i$$$, $$$1\leq d\leq 10^4$$$) — junctions that are connected by a street and the length of this street. It is guaranteed that each pair of junctions is connected by at most one street. It is guaranteed that you can get from any junctions to any other.
输出
Print one number — the minimal possible maximum distance that you need to pass to get from any junction to the nearest ice cream shop. Sonya's shops must form a simple path and the number of shops must be at most $$$k$$$.
示例
输入 #1
6 2 1 2 3 2 3 4 4 5 2 4 6 3 2 4 6
输出 #1
4
输入 #2
10 3 1 2 5 5 7 2 3 2 6 10 6 3 3 8 1 6 4 2 4 1 6 6 9 4 5 2 5
输出 #2
7
注意
In the first example, you can choose the path 2-4, so the answer will be 4.
第一个例子。
In the second example, you can choose the path 4-1-2, so the answer will be 7.
第二个例子。