{"raw_statement":[{"iden":"statement","content":"Sonya likes ice cream very much. She eats it even during programming competitions. That is why the girl decided that she wants to open her own ice cream shops.\n\nSonya lives in a city with $n$ junctions and $n-1$ streets between them. All streets are two-way and connect two junctions. It is possible to travel from any junction to any other using one or more streets. City Hall allows opening shops only on junctions. The girl cannot open shops in the middle of streets.\n\nSonya has exactly $k$ friends whom she can trust. If she opens a shop, one of her friends has to work there and not to allow anybody to eat an ice cream not paying for it. Since Sonya does not want to skip an important competition, she will not work in shops personally.\n\nSonya wants all her ice cream shops to form a simple path of the length $r$ ($1 \\le r \\le k$), i.e. to be located in different junctions $f_1, f_2, \\dots, f_r$ and there is street between $f_i$ and $f_{i+1}$ for each $i$ from $1$ to $r-1$.\n\nThe girl takes care of potential buyers, so she also wants to minimize the maximum distance between the junctions to the nearest ice cream shop. The distance between two junctions $a$ and $b$ is equal to the sum of all the street lengths that you need to pass to get from the junction $a$ to the junction $b$. So Sonya wants to _minimize_\n\n\\\\max_{a} \\\\min_{1 \\\\le i \\\\le r} d_{a,f_i}\n\nwhere $a$ takes a value of all possible $n$ junctions, $f_i$ — the junction where the $i$\\-th Sonya's shop is located, and $d_{x,y}$ — the distance between the junctions $x$ and $y$.\n\nSonya 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."},{"iden":"input","content":"The first line contains two integers $n$ and $k$ ($1\\leq k\\leq n\\leq 10^5$) — the number of junctions and friends respectively.\n\nEach 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."},{"iden":"output","content":"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$."},{"iden":"examples","content":"Input\n\n6 2\n1 2 3\n2 3 4\n4 5 2\n4 6 3\n2 4 6\n\nOutput\n\n4\n\nInput\n\n10 3\n1 2 5\n5 7 2\n3 2 6\n10 6 3\n3 8 1\n6 4 2\n4 1 6\n6 9 4\n5 2 5\n\nOutput\n\n7"},{"iden":"note","content":"In the first example, you can choose the path 2-4, so the answer will be 4.\n\n The first example.In the second example, you can choose the path 4-1-2, so the answer will be 7.\n\n The second example."}],"translated_statement":[{"iden":"statement","content":"Sonya 非常喜欢冰淇淋。即使在编程竞赛期间，她也会吃冰淇淋。因此，她决定开设自己的冰淇淋店。\n\nSonya 生活在一个有 $n$ 个交叉口和 $n -1$ 条街道的城市中。所有街道都是双向的，连接两个交叉口。从任意交叉口出发，都可以通过一条或多条街道到达其他任意交叉口。市政厅只允许在交叉口开设店铺，女孩不能在街道中间开设店铺。\n\nSonya 恰好有 $k$ 个可以信赖的朋友。如果她开设一家店，就必须有一位朋友在那里工作，以防止任何人不付钱就吃冰淇淋。由于 Sonya 不想错过重要的比赛，她不会亲自在店里工作。\n\nSonya 希望她所有的冰淇淋店形成一条长度为 $r$（$1 lt.eq r lt.eq k$）的简单路径，即位于不同的交叉口 $f_1, f_2, dots.h, f_r$ 上，并且对于每个 $i$ 从 $1$ 到 $r -1$，$f_i$ 和 $f_{i + 1}$ 之间都有一条街道相连。\n\n女孩也关心潜在的顾客，因此她希望最小化任意交叉口到最近冰淇淋店的最大距离。两个交叉口 $a$ 和 $b$ 之间的距离等于从交叉口 $a$ 到交叉口 $b$ 所需经过的所有街道长度之和。因此，Sonya 希望 _最小化_\n\n$$\\max_{a} \\min_{1 \\le i \\le r} d_{a,f_i}$$\n\n其中 $a$ 取遍所有 $n$ 个交叉口，$f_i$ 是第 $i$ 家 Sonya 店铺所在的交叉口，$d_{x, y}$ 是交叉口 $x$ 和 $y$ 之间的距离。\n\nSonya 不确定自己能否找到最优的店铺位置，因此她请求你帮助她开设不超过 $k$ 家店铺，使这些店铺形成一条简单路径，并使得任意交叉口到最近店铺的最大距离尽可能小。\n\n第一行包含两个整数 $n$ 和 $k$（$1 lt.eq k lt.eq n lt.eq 10^5$）——交叉口数量和朋友数量。\n\n接下来的 $n -1$ 行每行包含三个整数 $u_i$, $v_i$ 和 $d_i$（$1 lt.eq u_i, v_i lt.eq n$, $v_i eq.not u_i$, $1 lt.eq d lt.eq 10^4$）——由一条街道连接的两个交叉口及其长度。保证任意两个交叉口之间最多只有一条街道，且任意两个交叉口之间均可相互到达。\n\n输出一个数字——从任意交叉口到最近冰淇淋店所需的最小可能最大距离。Sonya 的店铺必须形成一条简单路径，且店铺数量不得超过 $k$。\n\n在第一个示例中，你可以选择路径 2-4，因此答案为 4。\n\n在第二个示例中，你可以选择路径 4-1-2，因此答案为 7。"},{"iden":"input","content":"第一行包含两个整数 $n$ 和 $k$（$1 lt.eq k lt.eq n lt.eq 10^5$）——交叉口数量和朋友数量。接下来的 $n -1$ 行每行包含三个整数 $u_i$, $v_i$ 和 $d_i$（$1 lt.eq u_i, v_i lt.eq n$, $v_i eq.not u_i$, $1 lt.eq d lt.eq 10^4$）——由一条街道连接的两个交叉口及其长度。保证任意两个交叉口之间最多只有一条街道，且任意两个交叉口之间均可相互到达。"},{"iden":"output","content":"输出一个数字——从任意交叉口到最近冰淇淋店所需的最小可能最大距离。Sonya 的店铺必须形成一条简单路径，且店铺数量不得超过 $k$。"},{"iden":"examples","content":"输入\n6 2\n1 2 3\n2 3 4\n4 5 2\n4 6 3\n2 4 6\n输出\n4\n\n输入\n10 3\n1 2 5\n5 7 2\n3 2 6\n10 6 3\n3 8 1\n6 4 2\n4 1 6\n6 9 4\n5 2 5\n输出\n7"},{"iden":"note","content":"在第一个示例中，你可以选择路径 2-4，因此答案为 4。 #cf_span(class=[tex-font-size-small], body=[The first example.]) 在第二个示例中，你可以选择路径 4-1-2，因此答案为 7。 #cf_span(class=[tex-font-size-small], body=[The second example.]) "}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions** \nLet $ G = (V, E) $ be a tree with $ |V| = n $ vertices (junctions) and $ |E| = n - 1 $ weighted edges (streets), where each edge $ (u, v) \\in E $ has a positive integer weight $ d(u, v) \\in [1, 10^4] $. \nLet $ k \\in \\mathbb{Z} $, $ 1 \\leq k \\leq n $, be the maximum number of shops (friends available). \n\nLet $ \\mathcal{P} $ be the set of all simple paths in $ G $ of length $ r $, where $ 1 \\leq r \\leq k $. \nFor a path $ P = (f_1, f_2, \\dots, f_r) \\in \\mathcal{P} $, define the set of shop locations as $ S_P = \\{f_1, f_2, \\dots, f_r\\} $. \n\nFor any vertex $ a \\in V $, define the distance from $ a $ to the nearest shop in $ S_P $ as: \n$$\nd(a, S_P) = \\min_{f_i \\in S_P} d(a, f_i)\n$$ \nwhere $ d(a, f_i) $ is the shortest path distance in $ G $ between vertices $ a $ and $ f_i $. \n\nDefine the maximum distance from any vertex to the nearest shop under path $ P $ as: \n$$\nD(P) = \\max_{a \\in V} d(a, S_P)\n$$\n\n**Constraints** \n1. $ 1 \\leq k \\leq n \\leq 10^5 $ \n2. The graph $ G $ is a tree. \n3. Each shop must be placed on a vertex. \n4. The set of shop locations must form a simple path of length $ r $, $ 1 \\leq r \\leq k $. \n\n**Objective** \nFind the minimum possible value of $ D(P) $ over all valid paths $ P \\in \\mathcal{P} $: \n$$\n\\min_{P \\in \\mathcal{P}} D(P)\n$$","simple_statement":null,"has_page_source":false}