問題文

うさぎはクリスマスに向けてクリスマスツリーを用意した．

賢明なる参加者諸氏はお気づきかもしれないが，クリスマスツリーとはもちろんグラフ理論における木構造のことである．ツリーは N 個の頂点 (頂点 1,\ 2,\ ...,\ N) からなり，N-1 本の辺を持つ．i (1 \leq i \leq N-1) 本目の辺は頂点 A_i と頂点 B_i を結ぶ長さ C_i の辺である．

うさぎは K 個の電球を持っており，それぞれの電球をツリーの頂点に置いて飾りつけようとしている．しかし，うさぎの持っている電球は非常に光量が大きいため，あまり電球どうしが近くなるとツリーが眩しくなりすぎてしまう．そこでうさぎは，電球どうしの距離をできるだけ遠ざけて電球を配置することにした．ここで，電球どうしの距離とは，電球が設置された頂点どうしの距離である．2 つの頂点間の距離は，片方の頂点からもう一方の頂点へツリーの辺を辿って行くときに，辿る辺の長さの和の最小値である．

N 個の頂点のうち K 個に電球を置いて光らせるとき，電球どうしの距離の最小値 d を考える．d として考えられる値のの最大値を求めよ．

制約

• 2 \leq K \leq N \leq 200,000．
• 1 \leq A_i, B_i \leq N．
• 1 \leq C_i \leq 5,000．
• A_i \neq B_i．
• 入力は木構造を表していることが保証される．

部分点

• N \leq 40,000 であるようなデータセットに正解した場合は，50 点が与えられる．
• 追加制約のないデータセットに正解した場合は，上記とは別に 50 点が与えられる．

入力例 1

4 3
2 1 100
3 2 200
4 2 300

出力例 1

300

頂点 1,\ 3,\ 4 に飾れば良い．

入力例 2

9 4
1 2 1
1 3 1
3 4 1
1 5 1
6 5 1
7 5 1
8 5 1
9 8 1

出力例 2

3

頂点 2,\ 4,\ 6,\ 9 に飾れば良い．

入力例 3

6 2
1 2 20
1 3 16
1 4 1224
4 5 1400
4 6 1700

出力例 3

3100

入力例 4

12 4
4 8 1214
12 7 890
3 1 651
5 9 1990
1 2 1671
4 1 55
6 4 761
7 2 862
11 10 1469
11 7 1122
12 9 364

出力例 4

2940