Se te da un árbol $T$ que consiste en $N$ vértices. Cada arista tiene un peso entero positivo.

Puedes realizar la siguiente operación en el árbol dado:

• Eliminar una arista del grafo y luego añadir una nueva arista entre dos vértices distintos cualesquiera. El peso de la nueva arista debe ser el mismo que el peso de la arista eliminada. El grafo resultante no necesita ser un árbol.

Definimos el peso de un camino como la suma de los pesos de las aristas en el camino. La distancia entre dos vértices $u$ y $v$ se define como el peso del camino más corto de $u$ a $v$ (el que tiene el peso mínimo). Si no existe tal camino, definimos la distancia como 0.

El peso de un grafo es el máximo de las distancias entre cualesquiera dos vértices.

Tu tarea es encontrar el mayor peso del grafo que se puede obtener realizando la operación exactamente $i$ veces, para $i = 0, 1, \dots, K$.

Entrada

La primera línea contiene dos enteros separados por espacios, $N$ y $K$.

La $i$-ésima de las siguientes $N - 1$ líneas contiene tres enteros separados por espacios, $u_i$, $v_i$ y $w_i$, que representan una arista no dirigida que conecta dos vértices diferentes $u_i$ y $v_i$ con un peso de $w_i$.

Se garantiza que las aristas forman un árbol.

• $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$)

Salida

Imprime $K + 1$ enteros separados por espacios. El $i$-ésimo entero debe ser igual al mayor peso del grafo que se puede obtener realizando la operación exactamente $i - 1$ veces.

Ejemplos

Entrada 1

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

Salida 1

14 16

Entrada 2

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

Salida 2

13 20 21