$K$개의 지하철 역

서울시장 한별은 혼잡한 도로의 교통 체증을 줄이기 위해 지하철을 건설하려 한다. 예산 문제로 역은 최대 $K$개까지만 지을 수 있고, 역들은 도로 하나의 경로로 모두 이어져야 한다.

서울의 도로망은 $N$개의 노드와 $N-1$개의 양방향 간선으로 이루어진 연결 그래프로 나타낸다. 노드는 건물, 간선은 도로이다. 한별은 $1 \le X \le K$를 만족하는 $X$개 노드의 단순 경로를 하나 골라, 그 경로에 있는 모든 노드에 역을 세워야 한다.

한별은 모든 건물에서 가장 가까운 역까지의 거리 중 최댓값을 최소로 만들고 싶어 한다. 이 값이 최소가 되도록 역의 위치를 정하는 프로그램을 작성하라.

첫째 줄에 두 정수 $N$과 $K$가 공백으로 구분되어 주어진다. $N$은 도시의 노드 수이고, $K$는 한별이 지을 수 있는 지하철 역의 최대 개수이다. ($1 \le K \le N \le 300\,000$)

이후 $N-1$개의 줄에 세 정수 $u_i$, $v_i$, $l_i$가 공백으로 구분되어 주어진다. 이는 $i$번째 도로가 노드 $u_i$와 $v_i$를 잇고, 길이가 $l_i$킬로미터라는 뜻이다. ($1 \le u_i, v_i \le N$; $1 \le l_i \le 10^{12}$; $i \ne j$이면 $\{u_i,v_i\} \ne \{u_j,v_j\}$)

모든 건물에서 가장 가까운 역까지의 거리 최댓값을 최소로 만들었을 때 그 값을 킬로미터 단위로 출력한다.

(서강대학교 학생용) 이 문제는 일반 프로그래밍 대회 형식에 맞게 변형한 문제이다. 시험에서의 원래 배점은 다음과 같았다.

• 부분문제 1: 55점
• 부분문제 2: 40점
• 부분문제 3: 3점
• 부분문제 4: 2점