E. Соня и магазины
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Соня очень любит мороженое. Она ест его даже во время соревнований по программированию. Поэтому, девочка решила, что хочет открыть свои собственные магазины мороженого.

Соня живет в городе, в котором всего $$$n$$$ перекрестков и $$$n-1$$$ улиц. Все улицы — двусторонние и соединяют пары перекрестков. С любого перекрестка можно попасть в любой другой перекресток в городе, пройдя по одной или более улиц. Мэрия позволяет открывать магазины только на перекрестках, девочка не может открывать магазины посреди улиц, между перекрестками.

У Сони есть ровно $$$k$$$ друзей, которым она доверяет. Если она откроет магазин, один с её друзей должен там работать и смотреть, чтобы никто не ел мороженое не заплатив. Поскольку Соня не хочет пропускать важные соревнования по программированию, непосредственно в магазинах она работать не будет.

Соня хочет, чтобы все её магазины мороженого образовали простой путь длины $$$r$$$ ($$$1 \le r \le k$$$), то есть были расположены в различных перекрёстках $$$f_1, f_2, \dots, f_r$$$ и существовала улица между $$$f_i$$$ и $$$f_{i+1}$$$ для всех $$$i$$$ от $$$1$$$ до $$$r-1$$$.

Девочка заботится о потенциальных покупателях, поэтому, она также хочет минимизировать максимальное расстояние от перекрестков до ближайшего магазина мороженого. Расстояние между двумя перекрестками $$$a$$$ и $$$b$$$ равно сумме длин всех улиц, которые нужно пройти, чтобы попасть с перекрестка $$$a$$$ на перекресток $$$b$$$. Таким образом, девочка хочет минимизировать

$$$$$$\max_{a} \min_{1 \le i \le r} d_{a,f_i}$$$$$$,

где $$$a$$$ принимает значение всевозможных $$$n$$$ перекрёстков, $$$f_i$$$ — перекресток с $$$i$$$-м магазином Сони, а $$$d_{x,y}$$$ — расстояние между перекрестками $$$x$$$ и $$$y$$$.

Соня неуверенна, что сможет найти оптимальные местоположения магазинов, поэтому, просит вас помочь ей открыть не более $$$k$$$ магазинов, которые образуют простой путь, и максимальное расстояние от произвольного перекрестка города до ближайшего магазина минимально.

Входные данные

Первая строка содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1\leq k\leq n\leq 10^5$$$) — количество перекрестков и друзей соответственно.

Каждая из следующих $$$n-1$$$ строк содержит три целых числа $$$u_i$$$, $$$v_i$$$ и $$$d_i$$$ ($$$1\leq u_i, v_i\leq n$$$, $$$v_i\neq u_i$$$, $$$1\leq d\leq 10^4$$$) — перекрестки, которые соединяет улица и длина этой улицы. Гарантируется, что между любой парой перекрестков не более одной улицы. Гарантируется, что можно доехать из любого перекрестка в любой другой, двигаясь только по улицам.

Выходные данные

Выведите одно число — минимальное максимальное расстояние, которое нужно будет пройти, чтобы попасть с любого перекрестка до ближайшего магазина мороженого. Магазины Сони должны располагаться вдоль произвольного простого пути из перекрестков длины не более $$$k$$$.

Примеры
Входные данные
6 2
1 2 3
2 3 4
4 5 2
4 6 3
2 4 6
Выходные данные
4
Входные данные
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
Выходные данные
7
Примечание

В первом примере можно выбрать путь 2-4, тогда ответ будет 4.

Первый пример.

Во втором примере можно выбрать путь 4-1-2, тогда ответ будет 7.

Второй пример.