On vous donne un arbre $T$ composé de $N$ sommets. Chaque arête possède un poids entier positif.

Vous pouvez effectuer l'opération suivante sur l'arbre donné : * Supprimer une arête du graphe, puis ajouter une nouvelle arête entre deux sommets distincts quelconques. Le poids de la nouvelle arête doit être identique au poids de l'arête supprimée. Le graphe résultant n'a pas besoin d'être un arbre.

Nous définissons le poids d'un chemin comme la somme des poids des arêtes sur ce chemin. La distance entre deux sommets $u$ et $v$ est définie comme le poids du chemin le plus court de $u$ à $v$ — ayant le poids minimum. S'il n'existe aucun chemin, nous définissons la distance comme 0.

Le poids d'un graphe est le maximum des distances entre deux sommets quelconques.

Votre tâche est de trouver le plus grand poids du graphe pouvant être obtenu en effectuant l'opération exactement $i$ fois, pour $i = 0, 1, \dots, K$.

Entrée

La première ligne contient deux entiers séparés par un espace, $N$ et $K$.

La $i$-ième des $N - 1$ lignes suivantes contient trois entiers séparés par un espace, $u_i$, $v_i$ et $w_i$, représentant une arête non orientée qui relie deux sommets différents $u_i$ et $v_i$ avec un poids de $w_i$.

Il est garanti que les arêtes forment un arbre.

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

Sortie

Affichez $K + 1$ entiers séparés par des espaces. Le $i$-ième entier doit être égal au plus grand poids du graphe pouvant être obtenu en effectuant l'opération exactement $i - 1$ fois.

Exemples

Entrée 1

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

Sortie 1

14 16

Entrée 2

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

Sortie 2

13 20 21