지역 (Regions)

JOI 나라에는 $N$ 개의 도시가 있고, $1$ 부터 $N$ 까지 번호가 붙어 있다. 이 도시들은 양방향으로 통행 가능한 도로로 트리 모양으로 연결되어 있다. 즉, 임의의 두 도시는 도로를 따라 서로 오갈 수 있고, 그 경로는 하나뿐이다. 이때 도로는 $N-1$ 개이다.

도시를 $M$ 개의 지역으로 나누려고 한다. 모든 지역은 하나 이상의 도시를 포함해야 하고, 모든 도시는 정확히 하나의 지역에 포함되어야 한다. 또한 같은 지역에 포함된 임의의 두 도시는 그 지역에 포함되지 않은 도시를 지나지 않고 도로를 따라 서로 오갈 수 있어야 한다.

각 지역의 지름의 최댓값 $d_{max}$ 가 가능한 한 작아지도록 지역을 나누려고 한다. 어떤 지역의 지름이란, 그 지역에 포함된 두 도시 사이의 거리의 최댓값이다. 두 도시 사이의 거리란, 두 도시를 잇는 경로에 포함된 도로 길이의 합이다. 지역에 도시가 하나만 포함되면 그 지역의 지름은 $0$ 으로 한다.

도로의 정보와 지역의 수가 주어지면, $d_{max}$ 의 최솟값을 계산하는 프로그램을 작성하시오.

표준 입력에서 다음 입력을 읽는다.

• 첫째 줄에는 정수 $N, M$ 이 공백을 구분으로 쓰여 있다.
• 이어지는 $N-1$ 개의 줄에는 한 줄에 하나의 도로에 대한 정보가 쓰여 있다. 이 줄들 중 $i$ 번째 줄은 도로 $i$ 에 대한 정보이며, 정수 $A_i, B_i, C_i$ 가 공백을 구분으로 쓰여 있다.

표준 출력에 $d_{max}$ 의 최솟값을 나타내는 정수 하나를 출력하시오.

• $2 \le N \le 30\,000$ (도시의 수)
• $2 \le M \le N$ (지역의 수)
• $1 \le A_i < B_i \le N$ (도로 $i$ 가 잇는 두 도시)
• $1 \le C_i \le 100$ (도로 $i$ 의 길이)