$K$ Subway Stations

Seoul City Mayor Hanbyeol plans to build a subway system to ease traffic congestion on the city's crowded roads. The budget allows at most $K$ stations, and all stations must be connected by a single path of roads.

Seoul is modeled as a connected graph with $N$ nodes and $N-1$ bidirectional edges, where each node is a building and each edge is a road. Hanbyeol must choose a simple path of $X$ nodes, where $1 \le X \le K$, and build a station on every node along that path.

Hanbyeol wants to minimize the maximum distance from any building to its nearest station. Write a program that finds the station placement that minimizes this value.

The first line contains two space-separated integers $N$, the number of nodes in the city, and $K$, the maximum number of subway stations Hanbyeol can build. ($1 \le K \le N \le 300\,000$)

Each of the next $N-1$ lines contains three space-separated integers $u_i$, $v_i$, and $l_i$. These mean that the $i$-th road connects nodes $u_i$ and $v_i$, and its length is $l_i$ kilometers. ($1 \le u_i, v_i \le N$; $1 \le l_i \le 10^{12}$; if $i \ne j$, then $\{u_i,v_i\} \ne \{u_j,v_j\}$)

Print the maximum distance from any building to its nearest station when this value is minimized, in kilometers.

(For Sogang students.) This problem is an adapted version that matches the format of a problem in a general programming contest. In the exam, the original scoring was:

• 55 points for Subtask 1.
• 40 points for Subtask 2.
• 3 points for Subtask 3.
• 2 points for Subtask 4.