시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 1024 MB43272158.333%

문제

정점이 $N$개인 트리가 주어진다. 각 정점은 1번부터 $N$번까지 차례대로 번호가 부여되어 있다. $i$번째 간선은 $A_i$번 정점과 $B_i$번 정점을 연결하며, 가중치는 $C_i$다. $(1 \leq i < N)$

트리에서 두 정점 사이의 거리는 그 둘을 잇는 최단경로 상의 간선의 가중치의 최댓값으로 정의한다. 단, 같은 두 정점 사이의 거리는 0으로 정의한다.

트리에 사는 사람들이 $N$개의 모임을 개최하려 한다. $i$번째 모임에는 1 이상 $i$ 이하의 번호를 가진 정점에 사는 사람들이 참석한다. 올해에는 코로나바이러스 전파 상황을 고려해 모임을 $X$개의 장소에서 각자 모인 후, 인터넷으로 진행하기로 했다. 각 모임은 트리 상의 서로 다른 $X$개의 정점 $v_1,\cdots,v_X$에서 이루어진다. 모임마다 고르는 정점은 독립적이다. 정점들이 정해지면 각 사람은 $v_1, \cdots, v_X$ 중 필요한 이동 거리가 최소인 정점 중 하나를 골라 이동하게 된다.

코로나바이러스 전파 상황에 따라 $X$의 값을 $1$부터 $K$까지의 값 중 하나로 정하기로 하였다. 모임을 미리 준비하기 위해 각 모임에 대해, $X$의 값이 $1$일 때부터 $K$일 때까지 사람들이 이동하는 거리의 최댓값의 최솟값의 합을 구하는 프로그램을 작성하시오.

입력

첫 줄에 트리의 정점 개수를 의미하는 정수 $N$과 정수 $K$가 사이에 공백을 두고 주어진다. $(1 \leq K \leq N \leq 300\,000)$

두번째 줄부터 $(N-1)$개의 줄에 걸쳐, 트리의 간선에 대한 정보가 주어진다. $(i+1)$번째 줄에는 세 개의 정수 $A_i,B_i,C_i$가 사이에 공백을 두고 주어진다. $(1 \leq i <N)$. 이는 $A_i$번 정점과 $B_i$번 정점을 연결하는 가중치 $C_i$의 간선이 존재함을 의미한다. $(1 \leq A_i,B_i,C_i \leq N)$

출력

첫 번째 줄부터 $N$개의 줄에 걸쳐, 답을 차례대로 출력한다. $i$번째 줄에는 $i$번째 모임에 대한 답을 출력한다 $(1 \leq i \leq N)$.

예제 입력 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
W3sicHJvYmxlbV9pZCI6IjIwNTU5IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjODE1XHVhZTMwIFx1YmFhOFx1Yzc4NCAyIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM4MTVcdWM4MTBcdWM3NzQgJE4kXHVhYzFjXHVjNzc4IFx1ZDJiOFx1YjlhY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWM4MTVcdWM4MTBcdWM3NDAgMVx1YmM4OFx1YmQ4MFx1ZDEzMCAkTiRcdWJjODhcdWFlNGNcdWM5YzAgXHVjYzI4XHViODQwXHViMzAwXHViODVjIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWJkODBcdWM1ZWNcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiAkaSRcdWJjODhcdWM5ZjggXHVhYzA0XHVjMTIwXHVjNzQwICRBX2kkXHViYzg4IFx1YzgxNVx1YzgxMFx1YWNmYyAkQl9pJFx1YmM4OCBcdWM4MTVcdWM4MTBcdWM3NDQgXHVjNWYwXHVhY2IwXHVkNTU4XHViYTcwLCBcdWFjMDBcdWM5MTFcdWNlNThcdWIyOTQgJENfaSRcdWIyZTQuICQoMSBcXGxlcSBpICZsdDsgTikkPFwvcD5cclxuXHJcbjxwPlx1ZDJiOFx1YjlhY1x1YzVkMFx1YzExYyBcdWI0NTAgXHVjODE1XHVjODEwIFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWFjNzBcdWI5YWNcdWIyOTQgXHVhZGY4IFx1YjQ1OFx1Yzc0NCBcdWM3ODdcdWIyOTQgXHVjZDVjXHViMmU4XHVhY2JkXHViODVjIFx1YzBjMVx1Yzc1OCBcdWFjMDRcdWMxMjBcdWM3NTggXHVhYzAwXHVjOTExXHVjZTU4XHVjNzU4IFx1Y2Q1Y1x1YjMxM1x1YWMxMlx1YzczY1x1Yjg1YyBcdWM4MTVcdWM3NThcdWQ1NWNcdWIyZTQuIFx1YjJlOCwgXHVhYzE5XHVjNzQwIFx1YjQ1MCBcdWM4MTVcdWM4MTAgXHVjMGFjXHVjNzc0XHVjNzU4IFx1YWM3MFx1YjlhY1x1YjI5NCAwXHVjNzNjXHViODVjIFx1YzgxNVx1Yzc1OFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkMmI4XHViOWFjXHVjNWQwIFx1YzBhY1x1YjI5NCBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NzQgJE4kXHVhYzFjXHVjNzU4IFx1YmFhOFx1Yzc4NFx1Yzc0NCBcdWFjMWNcdWNkNWNcdWQ1NThcdWI4MjQgXHVkNTVjXHViMmU0LiAkaSRcdWJjODhcdWM5ZjggXHViYWE4XHVjNzg0XHVjNWQwXHViMjk0IDEgXHVjNzc0XHVjMGMxICRpJCBcdWM3NzRcdWQ1NThcdWM3NTggXHViYzg4XHVkNjM4XHViOTdjIFx1YWMwMFx1YzljNCBcdWM4MTVcdWM4MTBcdWM1ZDAgXHVjMGFjXHViMjk0IFx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc3NCBcdWNjMzhcdWMxMWRcdWQ1NWNcdWIyZTQuIFx1YzYyY1x1ZDU3NFx1YzVkMFx1YjI5NCBcdWNmNTRcdWI4NWNcdWIwOThcdWJjMTRcdWM3NzRcdWI3ZWNcdWMyYTQgXHVjODA0XHVkMzBjIFx1YzBjMVx1ZDY2OVx1Yzc0NCBcdWFjZTBcdWI4MjRcdWQ1NzQgXHViYWE4XHVjNzg0XHVjNzQ0ICRYJFx1YWMxY1x1Yzc1OCBcdWM3YTVcdWMxOGNcdWM1ZDBcdWMxMWMgXHVhYzAxXHVjNzkwIFx1YmFhOFx1Yzc3OCBcdWQ2YzQsIFx1Yzc3OFx1ZDEzMFx1YjEzN1x1YzczY1x1Yjg1YyBcdWM5YzRcdWQ1ODlcdWQ1NThcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LiBcdWFjMDEgXHViYWE4XHVjNzg0XHVjNzQwIFx1ZDJiOFx1YjlhYyBcdWMwYzFcdWM3NTggXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCAkWCRcdWFjMWNcdWM3NTggXHVjODE1XHVjODEwICR2XzEsXFxjZG90cyx2X1gkXHVjNWQwXHVjMTFjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNFx1YjJlNC4gXHViYWE4XHVjNzg0XHViOWM4XHViMmU0IFx1YWNlMFx1Yjk3NFx1YjI5NCBcdWM4MTVcdWM4MTBcdWM3NDAgXHViM2M1XHViOWJkXHVjODAxXHVjNzc0XHViMmU0LiBcdWM4MTVcdWM4MTBcdWI0ZTRcdWM3NzQgXHVjODE1XHVkNTc0XHVjOWMwXHViYTc0IFx1YWMwMSBcdWMwYWNcdWI3OGNcdWM3NDAgJHZfMSwgXFxjZG90cywgdl9YJCBcdWM5MTEgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1Yzc3NFx1YjNkOSBcdWFjNzBcdWI5YWNcdWFjMDAgXHVjZDVjXHVjMThjXHVjNzc4IFx1YzgxNVx1YzgxMCBcdWM5MTEgXHVkNTU4XHViMDk4XHViOTdjIFx1YWNlOFx1Yjc3YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWFjOGMgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNmNTRcdWI4NWNcdWIwOThcdWJjMTRcdWM3NzRcdWI3ZWNcdWMyYTQgXHVjODA0XHVkMzBjIFx1YzBjMVx1ZDY2OVx1YzVkMCBcdWI1MzBcdWI3N2MgJFgkXHVjNzU4IFx1YWMxMlx1Yzc0NCAkMSRcdWJkODBcdWQxMzAgJEskXHVhZTRjXHVjOWMwXHVjNzU4IFx1YWMxMiBcdWM5MTEgXHVkNTU4XHViMDk4XHViODVjIFx1YzgxNVx1ZDU1OFx1YWUzMFx1Yjg1YyBcdWQ1NThcdWM2MDBcdWIyZTQuIFx1YmFhOFx1Yzc4NFx1Yzc0NCBcdWJiZjhcdWI5YWMgXHVjOTAwXHViZTQ0XHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWFjMDEgXHViYWE4XHVjNzg0XHVjNWQwIFx1YjMwMFx1ZDU3NCwgJFgkXHVjNzU4IFx1YWMxMlx1Yzc3NCAkMSRcdWM3N2MgXHViNTRjXHViZDgwXHVkMTMwICRLJFx1Yzc3YyBcdWI1NGNcdWFlNGNcdWM5YzAgXHVjMGFjXHViNzhjXHViNGU0XHVjNzc0IFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjI5NCBcdWFjNzBcdWI5YWNcdWM3NTggXHVjZDVjXHViMzEzXHVhYzEyXHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc1OCBcdWQ1NjlcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIFx1ZDJiOFx1YjlhY1x1Yzc1OCBcdWM4MTVcdWM4MTAgXHVhYzFjXHVjMjE4XHViOTdjIFx1Yzc1OFx1YmJmOFx1ZDU1OFx1YjI5NCBcdWM4MTVcdWMyMTggJE4kXHVhY2ZjIFx1YzgxNVx1YzIxOCAkSyRcdWFjMDAgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWI0NTBcdWFjZTAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAkKDEgXFxsZXEgSyBcXGxlcSBOIFxcbGVxIDMwMFxcLDAwMCkkPFwvcD5cclxuXHJcbjxwPlx1YjQ1MFx1YmM4OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgJChOLTEpJFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwLCBcdWQyYjhcdWI5YWNcdWM3NTggXHVhYzA0XHVjMTIwXHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAkKGkrMSkkXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMxMzggXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCAkQV9pLEJfaSxDX2kkXHVhYzAwIFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWFjZjVcdWJjMzFcdWM3NDQgXHViNDUwXHVhY2UwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gJCgxIFxcbGVxIGkgJmx0O04pJC4gXHVjNzc0XHViMjk0ICRBX2kkXHViYzg4IFx1YzgxNVx1YzgxMFx1YWNmYyAkQl9pJFx1YmM4OCBcdWM4MTVcdWM4MTBcdWM3NDQgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1YWMwMFx1YzkxMVx1Y2U1OCAkQ19pJFx1Yzc1OCBcdWFjMDRcdWMxMjBcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTY4XHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4gJCgxIFxcbGVxIEFfaSxCX2ksQ19pIFxcbGVxIE4pJDxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwICROJFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwLCBcdWIyZjVcdWM3NDQgXHVjYzI4XHViODQwXHViMzAwXHViODVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gJGkkXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCAkaSRcdWJjODhcdWM5ZjggXHViYWE4XHVjNzg0XHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWIyZjVcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0ICQoMSBcXGxlcSBpIFxcbGVxIE4pJC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyMDU1OSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJlc3QgTWVldGluZyBQbGFjZXMiLCJkZXNjcmlwdGlvbiI6IjxwPkEgdHJlZSB3aXRoICROJCB2ZXJ0aWNlcyBpcyBnaXZlbi4gVmVydGljZXMgYXJlIG51bWJlcmVkIHNlcXVlbnRpYWxseSBmcm9tICQxJCB0byAkTiQuIFRoZSAkaSQtdGggZWRnZSBjb25uZWN0cyB2ZXJ0aWNlcyAkQV9pJCBhbmQgJEJfaSQsIGFuZCBoYXMgd2VpZ2h0ICRDX2kkLCBmb3IgJDEgXFxsZXEgaSBcXGxlcSBOIC0gMSQuPFwvcD5cclxuXHJcbjxwPlRoZSA8ZW0+dGVsZXBvcnQgZGlzdGFuY2U8XC9lbT4gYmV0d2VlbiB0d28gdmVydGljZXMgb2YgdGhlIHRyZWUgaXMgdGhlIG1heGltdW0gd2VpZ2h0IG9mIHRoZSBlZGdlIG9uIHRoZSBzaG9ydGVzdCBwYXRoIGNvbm5lY3RpbmcgdGhlbS4gVGhlIHRlbGVwb3J0IGRpc3RhbmNlIGJldHdlZW4gYSB2ZXJ0ZXggYW5kIGl0c2VsZiBpcyBkZWZpbmVkIGFzICQwJC48XC9wPlxyXG5cclxuPHA+UGVvcGxlIGxpdmluZyBvbiB0aGUgdHJlZSB3YW50IHRvIGhvbGQgJE4kIG1lZXRpbmdzLiBUaGUgJGkkLXRoIG1lZXRpbmcgaXMgYXR0ZW5kZWQgYnkgcGVvcGxlIGxpdmluZyBpbiB0aGUgdmVydGljZXMgbnVtYmVyZWQgZnJvbSAkMSQgdG8gJGkkLiBUaGlzIHllYXIsIGJlY2F1c2Ugb2YgdGhlIHNwcmVhZCBvZiBjb3JvbmF2aXJ1cywgdGhlIG1lZXRpbmcgcGFydGljaXBhbnRzIHdpbGwgYXJyaXZlIGF0ICRYJCBzZWxlY3RlZCBsb2NhdGlvbnMsIGFuZCB0aGVuIGNvbm5lY3QgdmlhIEludGVybmV0IGZyb20gdGhlc2UgbG9jYXRpb25zLjxcL3A+XHJcblxyXG48cD5Nb3JlIGZvcm1hbGx5LCBmb3IgZWFjaCBtZWV0aW5nLCB3ZSB3aWxsIGNob29zZSAkWCQgcGFpcndpc2UgZGlzdGluY3QgdmVydGljZXMgJHZfMSQsICR2XzIkLCAkXFxsZG90cyQsICR2X1gkLiBPbmNlIHRoZSB2ZXJ0aWNlcyBhcmUgZGV0ZXJtaW5lZCwgZWFjaCBwZXJzb24gd2lsbCBtb3ZlIHRvIG9uZSBvZiB0aGUgdmVydGljZXMgJHZfMSQsICRcXGxkb3RzJCwgJHZfWCQgd2l0aCB0aGUgbWluaW11bSB0ZWxlcG9ydCBkaXN0YW5jZSB0byBpdC4gTGV0IHVzIGRlZmluZSB0aGUgPGVtPm1lZXRpbmcgY29zdDxcL2VtPiBmb3IgdGhlIGdpdmVuICRYJCBhbmQgJGkkIGFzIHRoZSBtYXhpbXVtIG9mIHRlbGVwb3J0IGRpc3RhbmNlcyBmb3IgbWVldGluZyBwYXJ0aWNpcGFudHMuIFdlIHdpbGwgc2VsZWN0IHRoZSB2ZXJ0aWNlcyAkdl8xJCwgJFxcbGRvdHMkLCAkdl9YJCBpbiBzdWNoIGEgd2F5IHRoYXQgdGhlIG1lZXRpbmcgY29zdCBpcyBtaW5pbWFsIHBvc3NpYmxlLjxcL3A+XHJcblxyXG48cD5UaGUgdmFsdWUgb2YgJFgkIGRlcGVuZHMgb24gdGhlIGNvcm9uYXZpcnVzIHNpdHVhdGlvbiwgYW5kIG1heSB2YXJ5IGZyb20gJDEkIHRvICRLJC4gVG8gcHJlcGFyZSBmb3IgdGhlIG1lZXRpbmcgaW4gYWR2YW5jZSwgd3JpdGUgYSBwcm9ncmFtIHRoYXQsIGZvciBlYWNoIG9mIHRoZSAkTiQgbWVldGluZ3MsIGZpbmRzIHRoZSBzdW0gb2YgdGhlIG1lZXRpbmcgY29zdHMgZm9yIGFsbCBwb3NzaWJsZSB2YWx1ZXMgb2YgJFgkIGZyb20gJDEkIHRvICRLJCwgaW5jbHVzaXZlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIGludGVnZXJzICROJCBhbmQgJEskOiB0aGUgbnVtYmVyIG9mIHZlcnRpY2VzIGFuZCB0aGUgdXBwZXIgbGltaXQgZm9yICRYJCwgcmVzcGVjdGl2ZWx5ICgkMSBcXGxlcSBLIFxcbGVxIE4gXFxsZXEgMyBcXGNkb3QgMTBeNSQpLjxcL3A+XHJcblxyXG48cD5UaGUgZm9sbG93aW5nICROIC0gMSQgbGluZXMgZGVzY3JpYmUgdGhlIHRyZWUuIEVhY2ggb2YgdGhlc2UgbGluZXMgY29udGFpbnMgdGhyZWUgaW50ZWdlcnMsICRBX2kkLCAkQl9pJCwgYW5kICRDX2kkLCB0ZWxsaW5nIHRoYXQgdGhlcmUgaXMgYW4gZWRnZSBiZXR3ZWVuIHZlcnRpY2VzICRBX2kkIGFuZCAkQl9pJCB3aXRoIHdlaWdodCAkQ19pJCAoJDEgXFxsZXEgQV9pLCBCX2ksIENfaSBcXGxlcSBOJCkuIEl0IGlzIGd1YXJhbnRlZWQgdGhhdCB0aGUgcmVzdWx0aW5nIGdyYXBoIGlzIGEgdHJlZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QcmludCAkTiQgbGluZXMuIE9uIGxpbmUgJGkkLCBwcmludCB0aGUgc3VtIG9mIG1lZXRpbmcgY29zdHMgb2YgJGkkLXRoIG1lZXRpbmcgZm9yIGFsbCAkWCQgZnJvbSAkMSQgdG8gJEskLCBpbmNsdXNpdmUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==