정기 모임 2

정점이 $N$개인 트리가 주어진다. 정점에는 1번부터 $N$번까지 번호가 붙어 있다. $i$번째 간선은 $A_i$번 정점과 $B_i$번 정점을 잇고, 가중치는 $C_i$이다. $(1 \leq i < N)$

두 정점 사이의 거리는 두 정점을 잇는 최단 경로에 있는 간선 가중치의 최댓값이다. 같은 정점 사이의 거리는 0이다.

트리에 사는 사람들이 $N$번의 모임을 연다. $i$번째 모임에는 1번부터 $i$번까지의 정점에 사는 사람들이 참석한다. 올해는 코로나바이러스 상황을 고려해, 각 모임을 $X$곳에서 직접 모인 뒤 온라인으로 이어 간다. 각 모임은 트리의 서로 다른 $X$개의 정점 $v_1, \cdots, v_X$에서 열린다. 모임마다 정점을 독립적으로 고른다. 정점이 정해지면 각 사람은 $v_1, \cdots, v_X$ 중 이동 거리가 가장 짧은 정점으로 이동한다.

$X$의 값은 1부터 $K$까지 중 하나이다. 각 모임에 대해, $X$를 1부터 $K$까지 바꿔 가며 사람들이 이동하는 거리의 최댓값의 최솟값을 구하고, 그 값들을 모두 더한 합을 구한다. 최솟값은 정점을 고르는 방법에 대해 취한다.

첫 줄에 정점 개수 $N$과 정수 $K$가 공백으로 구분되어 주어진다. $(1 \leq K \leq N \leq 300\,000)$

둘째 줄부터 $N-1$개의 줄에 간선 정보가 주어진다. $i+1$번째 줄에는 정수 $A_i$, $B_i$, $C_i$가 공백으로 구분되어 주어진다. 이는 $A_i$번 정점과 $B_i$번 정점을 가중치 $C_i$인 간선으로 잇는다는 뜻이다. $(1 \leq i < N)$ $(1 \leq A_i, B_i, C_i \leq N)$

$N$개의 줄에 걸쳐 답을 차례대로 출력한다. $i$번째 줄에는 $i$번째 모임의 답을 출력한다. $(1 \leq i \leq N)$