$N$개의 정점으로 이루어진 트리 $T$가 주어진다. 각 간선은 양의 정수 가중치를 가진다. 주어진 트리에 대해 다음 연산을 수행할 수 있다.

• 그래프에서 간선 하나를 삭제한 뒤, 임의의 두 서로 다른 정점 사이에 새로운 간선을 추가한다. 이때 새로운 간선의 가중치는 삭제한 간선의 가중치와 같아야 한다. 결과로 얻어지는 그래프는 트리일 필요는 없다.

경로의 가중치는 경로에 포함된 간선들의 가중치 합으로 정의한다. 두 정점 $u$와 $v$ 사이의 거리는 $u$에서 $v$까지의 최단 경로(가중치가 최소인 경로)의 가중치로 정의한다. 만약 그러한 경로가 없다면 거리는 0으로 정의한다. 그래프의 가중치는 임의의 두 정점 사이의 거리 중 최댓값으로 정의한다.

당신의 임무는 연산을 정확히 $i$번 수행하여 얻을 수 있는 그래프의 최대 가중치를 $i = 0, 1, \dots, K$에 대해 각각 구하는 것이다.

입력

첫 번째 줄에는 두 개의 정수 $N$과 $K$가 공백으로 구분되어 주어진다. 이어지는 $N - 1$개의 줄의 $i$번째 줄에는 세 개의 정수 $u_i, v_i, w_i$가 공백으로 구분되어 주어지며, 이는 서로 다른 두 정점 $u_i$와 $v_i$를 잇는 가중치 $w_i$의 무방향 간선을 의미한다. 주어지는 간선들은 트리를 형성함이 보장된다.

• $2 \le N \le 2000$
• $0 \le K \le 2000$
• $1 \le u_i < v_i \le N$ ($1 \le i \le N - 1$)
• $1 \le w_i \le 10^9$ ($1 \le i \le N - 1$)

출력

$K + 1$개의 정수를 공백으로 구분하여 출력한다. $i$번째 정수는 연산을 정확히 $i - 1$번 수행하여 얻을 수 있는 그래프의 최대 가중치여야 한다.

예제

입력 1

5 1
1 3 2
4 5 4
3 4 3
2 3 7

출력 1

14 16

입력 2

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

출력 2

13 20 21