$N$개의 정점을 가진 트리가 주어진다. 정점은 1부터 $N$까지 순서대로 번호가 매겨져 있다. $i$번째 간선은 정점 $A_i$와 $B_i$를 연결하며, 가중치 $C_i$를 가진다 ($1 \le i \le N - 1$).

두 정점 사이의 텔레포트 거리(teleport distance)는 두 정점을 잇는 최단 경로 상에 있는 간선의 최대 가중치로 정의된다. 정점과 자기 자신 사이의 텔레포트 거리는 0으로 정의된다.

트리에 거주하는 사람들은 $N$번의 모임을 가지려 한다. $i$번째 모임에는 1부터 $i$까지 번호가 매겨진 정점에 사는 사람들이 참석한다. 올해는 코로나바이러스 확산으로 인해, 모임 참가자들은 $X$개의 선택된 위치로 모인 뒤, 그곳에서 인터넷을 통해 연결될 것이다.

더 형식적으로 말하자면, 각 모임마다 우리는 서로 다른 $X$개의 정점 $v_1, v_2, \dots, v_X$를 선택할 것이다. 정점들이 결정되면, 각 사람은 자신과 텔레포트 거리가 최소인 정점 $v_1, \dots, v_X$ 중 하나로 이동할 것이다. 주어진 $X$와 $i$에 대한 모임 비용(meeting cost)을 모임 참가자들의 텔레포트 거리 중 최댓값으로 정의하자. 우리는 모임 비용이 최소가 되도록 정점 $v_1, \dots, v_X$를 선택할 것이다.

$X$의 값은 코로나바이러스 상황에 따라 달라지며, 1부터 $K$까지 변할 수 있다. 모임을 미리 준비하기 위해, 각 $N$번의 모임에 대하여 $X$가 1부터 $K$까지 가능한 모든 값에 대한 모임 비용의 합을 구하는 프로그램을 작성하라.

입력

첫 번째 줄에는 정점의 수 $N$과 $X$의 상한인 $K$가 주어진다 ($1 \le K \le N \le 3 \cdot 10^5$).

다음 $N - 1$줄은 트리를 설명한다. 각 줄에는 세 정수 $A_i, B_i, C_i$가 주어지며, 이는 정점 $A_i$와 $B_i$ 사이에 가중치 $C_i$인 간선이 있음을 의미한다 ($1 \le A_i, B_i, C_i \le N$). 주어진 그래프는 트리임이 보장된다.

출력

$N$줄을 출력한다. $i$번째 줄에는 $i$번째 모임에 대하여 $X$가 1부터 $K$까지일 때의 모임 비용의 합을 출력한다.

예제

입력 1

10 4
5 1 2
1 6 4
6 2 1
2 8 9
8 3 5
3 4 8
4 10 9
10 9 8
9 7 7

출력 1

0
4
13
21
23
23
30
31
33
34

입력 2

8 3
7 3 4
4 5 2
3 6 1
6 8 6
8 5 1
2 5 8
1 5 2

출력 2

0
8
14
16
16
16
18
18