Alex is planning rest area placements on a simplified model of Taiwan's freeway system. The system contains $$$n$$$ interchanges, connected by $$$n - 1$$$ bidirectional roads. The network is connected, and there is exactly one shortest route between any pair of interchanges. The $$$i$$$-th road connects interchanges $$$u_i$$$ and $$$v_i$$$, and has a length of $$$l_i$$$.

Exactly $$$k$$$ rest areas with gas stations can be built, each located at an interchange. A driver may start a trip from any interchange and travel to any other, always following the unique shortest path. They begin each trip with a full tank of gas and can refuel only at interchanges that have a rest area.

Alex is curious about the smallest possible fuel tank capacity $$$d$$$ such that it's possible to place the $$$k$$$ rest areas in a way that ensures no driver will ever run out of gas. On any trip, the driver must never have to travel more than $$$d$$$ units along the path without passing through a rest area, including at the beginning or end of the journey. The goal is to figure out the minimum such $$$d$$$, assuming the rest areas are placed in the best possible way.