Diberikan sebuah pohon dengan $N$ simpul. Simpul-simpul diberi nomor berurutan dari $1$ hingga $N$. Sisi ke-$i$ menghubungkan simpul $A_i$ dan $B_i$, serta memiliki bobot $C_i$, untuk $1 \le i \le N - 1$.

Jarak teleportasi antara dua simpul pohon adalah bobot maksimum sisi pada jalur terpendek yang menghubungkan keduanya. Jarak teleportasi antara sebuah simpul dan dirinya sendiri didefinisikan sebagai $0$.

Penduduk yang tinggal pada pohon ingin mengadakan $N$ pertemuan. Pertemuan ke-$i$ dihadiri penduduk yang tinggal pada simpul bernomor $1$ hingga $i$. Tahun ini, karena penyebaran virus korona, para peserta pertemuan akan mendatangi $X$ lokasi terpilih, lalu terhubung melalui Internet dari lokasi-lokasi tersebut.

Secara lebih formal, untuk setiap pertemuan kita memilih $X$ simpul berbeda satu sama lain $v_1, v_2, \ldots, v_X$. Setelah simpul-simpul ditentukan, setiap orang akan berpindah ke salah satu simpul $v_1, \ldots, v_X$ yang jarak teleportasinya dari orang tersebut minimum. Definisikan biaya pertemuan untuk $X$ dan $i$ yang diberikan sebagai jarak teleportasi maksimum di antara para peserta pertemuan. Kita memilih simpul $v_1, \ldots, v_X$ agar biaya pertemuan sekecil mungkin.

Nilai $X$ bergantung pada situasi virus korona dan dapat bervariasi dari $1$ hingga $K$. Untuk mempersiapkan pertemuan sebelumnya, tulis program yang, untuk setiap pertemuan dari $N$ pertemuan, mencari jumlah biaya pertemuan untuk semua nilai $X$ yang mungkin dari $1$ hingga $K$, inklusif.

Masukan

Baris pertama masukan berisi dua bilangan bulat $N$ dan $K$: berturut-turut banyaknya simpul dan batas atas $X$ ($1 \le K \le N \le 3 \cdot 10^5$).

Sebanyak $N - 1$ baris berikutnya menjelaskan pohon. Setiap baris berisi tiga bilangan bulat $A_i$, $B_i$, dan $C_i$, yang menyatakan bahwa ada sisi antara simpul $A_i$ dan $B_i$ dengan bobot $C_i$ ($1 \le A_i, B_i, C_i \le N$). Dijamin bahwa graf yang terbentuk adalah pohon.

Keluaran

Cetak $N$ baris. Pada baris $i$, cetak jumlah biaya pertemuan ke-$i$ untuk semua $X$ dari $1$ hingga $K$, inklusif.

Contoh

Masukan 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

Keluaran 1

0
4
13
21
23
23
30
31
33
34

Masukan 2

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

Keluaran 2

0
8
14
16
16
16
18
18