시간 제한메모리 제한제출정답맞힌 사람정답 비율
1.5 초 128 MB33418615255.678%

문제

로스팅하는 엠마는 바리스타입니다. 엠마는 N개의 정점을 가진 트리 형태의 농장 연결 시스템을 구축한 상태입니다. 트리의 정점은 1번부터 N번까지 번호가 매겨져 있습니다. 각각의 간선은 그 농장에서 다른 농장으로 이동할 수 있음을 뜻하며, 간선의 가중치는 이동 거리를 뜻합니다.

엠마는 한 개의 농장을 정해 농장 옆에 로스팅 시설을 마련하려고 합니다. 이때, 다른 농장에서 로스팅 시설까지의 거리의 합들을 알아야, 효율적으로 로스팅 시설의 위치를 정할 수 있을 것입니다. 그러므로 각각의 농장마다 다른 농장들에서 그 농장으로 가는 최단 거리들의 합을 구해줍시다.

입력

첫째 줄에 N이 입력됩니다. (1 ≤ N ≤ 3 × 105)

N-1 줄 동안 세 수 u, vd가 주어집니다. 이는 u번째 농장과 v번째 농장은 서로 연결되어 있으며, 그 거리는 d임을 뜻합니다. (1 ≤ u, v ≤ N, 1 ≤ d ≤ 5)

주어지는 그래프는 트리입니다.

출력

N개의 줄 동안 각각의 농장에 대해 다른 농장들에서 그 농장으로 가는 최단 거리들의 합을 출력합니다.

예제 입력 1

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

예제 출력 1

19
17
25
19
27
23
27
27
31
31
W3sicHJvYmxlbV9pZCI6IjE1NjQ3IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViODVjXHVjMmE0XHVkMzA1XHVkNTU4XHViMjk0IFx1YzVlMFx1YjljOFx1YjNjNCBcdWJjMTRcdWI5YWNcdWMyYTRcdWQwYzBcdWM3ODVcdWIyYzhcdWIyZTQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1Yjg1Y1x1YzJhNFx1ZDMwNVx1ZDU1OFx1YjI5NCBcdWM1ZTBcdWI5YzhcdWIyOTQgXHViYzE0XHViOWFjXHVjMmE0XHVkMGMwXHVjNzg1XHViMmM4XHViMmU0LiBcdWM1ZTBcdWI5YzhcdWIyOTQgPGVtPk48XC9lbT5cdWFjMWNcdWM3NTggXHVjODE1XHVjODEwXHVjNzQ0IFx1YWMwMFx1YzljNCBcdWQyYjhcdWI5YWMgXHVkNjE1XHVkMGRjXHVjNzU4IFx1YjE4ZFx1YzdhNSBcdWM1ZjBcdWFjYjAgXHVjMmRjXHVjMmE0XHVkMTVjXHVjNzQ0IFx1YWQ2Y1x1Y2Q5NVx1ZDU1YyBcdWMwYzFcdWQwZGNcdWM3ODVcdWIyYzhcdWIyZTQuIFx1ZDJiOFx1YjlhY1x1Yzc1OCBcdWM4MTVcdWM4MTBcdWM3NDAgMVx1YmM4OFx1YmQ4MFx1ZDEzMCBOXHViYzg4XHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWI5ZTRcdWFjYThcdWM4MzggXHVjNzg4XHVjMmI1XHViMmM4XHViMmU0LiZuYnNwO1x1YWMwMVx1YWMwMVx1Yzc1OCBcdWFjMDRcdWMxMjBcdWM3NDAgXHVhZGY4IFx1YjE4ZFx1YzdhNVx1YzVkMFx1YzExYyBcdWIyZTRcdWI5NzggXHViMThkXHVjN2E1XHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHVjNzRjXHVjNzQ0IFx1YjczYlx1ZDU1OFx1YmE3MCwgXHVhYzA0XHVjMTIwXHVjNzU4IFx1YWMwMFx1YzkxMVx1Y2U1OFx1YjI5NCBcdWM3NzRcdWIzZDkgXHVhYzcwXHViOWFjXHViOTdjIFx1YjczYlx1ZDU2OVx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNWUwXHViOWM4XHViMjk0IFx1ZDU1YyBcdWFjMWNcdWM3NTggXHViMThkXHVjN2E1XHVjNzQ0IFx1YzgxNVx1ZDU3NCBcdWIxOGRcdWM3YTUgXHVjNjA2XHVjNWQwIFx1Yjg1Y1x1YzJhNFx1ZDMwNSBcdWMyZGNcdWMxMjRcdWM3NDQgXHViOWM4XHViODI4XHVkNTU4XHViODI0XHVhY2UwIFx1ZDU2OVx1YjJjOFx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWIyZTRcdWI5NzggXHViMThkXHVjN2E1XHVjNWQwXHVjMTFjIFx1Yjg1Y1x1YzJhNFx1ZDMwNSBcdWMyZGNcdWMxMjRcdWFlNGNcdWM5YzBcdWM3NTggXHVhYzcwXHViOWFjXHVjNzU4IFx1ZDU2OVx1YjRlNFx1Yzc0NCBcdWM1NGNcdWM1NDRcdWM1N2MsIFx1ZDZhOFx1YzcyOFx1YzgwMVx1YzczY1x1Yjg1YyBcdWI4NWNcdWMyYTRcdWQzMDUgXHVjMmRjXHVjMTI0XHVjNzU4IFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWM4MTVcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1Yzc0NCBcdWFjODNcdWM3ODVcdWIyYzhcdWIyZTQuIFx1YWRmOFx1YjdlY1x1YmJjMFx1Yjg1YyBcdWFjMDFcdWFjMDFcdWM3NTggXHViMThkXHVjN2E1XHViOWM4XHViMmU0IFx1YjJlNFx1Yjk3OCBcdWIxOGRcdWM3YTVcdWI0ZTRcdWM1ZDBcdWMxMWMgXHVhZGY4IFx1YjE4ZFx1YzdhNVx1YzczY1x1Yjg1YyBcdWFjMDBcdWIyOTQgXHVjZDVjXHViMmU4IFx1YWM3MFx1YjlhY1x1YjRlNFx1Yzc1OCBcdWQ1NjlcdWM3NDQgXHVhZDZjXHVkNTc0XHVjOTBkXHVjMmRjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCA8ZW0+TjxcL2VtPlx1Yzc3NCBcdWM3ODVcdWI4MjVcdWI0MjlcdWIyYzhcdWIyZTQuJm5ic3A7KDEmdGhpbnNwOyZsZTsmdGhpbnNwOzxlbT5OPFwvZW0+JnRoaW5zcDsmbGU7JnRoaW5zcDszJnRoaW5zcDsmdGltZXM7JnRoaW5zcDsxMDxzdXA+NTxcL3N1cD4pPFwvcD5cclxuXHJcbjxwPjxlbT5OPFwvZW0+LTEgXHVjOTA0IFx1YjNkOVx1YzU0OCBcdWMxMzggXHVjMjE4IDxlbT51PFwvZW0+LCA8ZW0+djxcL2VtPiBcdWM2NDAgPGVtPmQ8XC9lbT5cdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWQxXHViMmM4XHViMmU0LiBcdWM3NzRcdWIyOTQgPGVtPnU8XC9lbT5cdWJjODhcdWM5ZjggXHViMThkXHVjN2E1XHVhY2ZjIDxlbT52PFwvZW0+XHViYzg4XHVjOWY4IFx1YjE4ZFx1YzdhNVx1Yzc0MCBcdWMxMWNcdWI4NWMgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVhZGY4IFx1YWM3MFx1YjlhY1x1YjI5NCA8ZW0+ZDxcL2VtPlx1Yzc4NFx1Yzc0NCBcdWI3M2JcdWQ1NjlcdWIyYzhcdWIyZTQuJm5ic3A7KDEmdGhpbnNwOyZsZTsmdGhpbnNwOzxlbT51PFwvZW0+LCZ0aGluc3A7PGVtPnY8XC9lbT4mdGhpbnNwOyZsZTsmdGhpbnNwOzxlbT5OPFwvZW0+LCZ0aGluc3A7MSZ0aGluc3A7JmxlOyZ0aGluc3A7PGVtPmQ8XC9lbT4mdGhpbnNwOyZsZTsmdGhpbnNwOzUpPFwvcD5cclxuXHJcbjxwPlx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWFkZjhcdWI3OThcdWQ1MDRcdWIyOTQgXHVkMmI4XHViOWFjXHVjNzg1XHViMmM4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPjxlbT5OPFwvZW0+XHVhYzFjXHVjNzU4IFx1YzkwNCBcdWIzZDlcdWM1NDggXHVhYzAxXHVhYzAxXHVjNzU4IFx1YjE4ZFx1YzdhNVx1YzVkMCBcdWIzMDBcdWQ1NzQgXHViMmU0XHViOTc4IFx1YjE4ZFx1YzdhNVx1YjRlNFx1YzVkMFx1YzExYyBcdWFkZjggXHViMThkXHVjN2E1XHVjNzNjXHViODVjIFx1YWMwMFx1YjI5NCBcdWNkNWNcdWIyZTggXHVhYzcwXHViOWFjXHViNGU0XHVjNzU4IFx1ZDU2OVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NjlcdWIyYzhcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTU2NDciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUcmVlIGFuZCBQYXRoIiwiZGVzY3JpcHRpb24iOiI8cD5BIHRyZWUgd2l0aCA8ZW0+TjxcL2VtPiB2ZXJ0aWNlcyAxIHRvIDxlbT5OPFwvZW0+IGlzIGdpdmVuLiBBbGwgdGhlIGVkZ2VzIGhhdmUgYSBkaXN0YW5jZSB3aGljaCBpcyBhdCBsZWFzdCAxLiBGb3IgZXZlcnkgdmVydGV4LCBjYWxjdWxhdGUgdGhlIHN1bSBvZiBtaW5pbXVtIGRpc3RhbmNlcyB0byB0aGF0IHZlcnRleCBmcm9tIGFsbCB2ZXJ0aWNlcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPjxlbT5OPFwvZW0+IGlzIGdpdmVuIGluIHRoZSBmaXJzdCBsaW5lLiAoMSAmbGU7IDxlbT5OPFwvZW0+ICZsZTsgMyAmdGltZXM7IDEwPHN1cD41PFwvc3VwPik8XC9wPlxyXG5cclxuPHA+Rm9yIHRoZSBuZXh0IDxlbT5OPFwvZW0+LTEgbGluZXMsIHRocmVlIG51bWJlcnMgPGVtPnU8XC9lbT4gYW5kIDxlbT52PFwvZW0+IGFuZCA8ZW0+ZDxcL2VtPiBpcyBnaXZlbi4gVGhpcyBtZWFucyB0aGF0IHRoZXJlIGlzIGFuIGVkZ2UgY29ubmVjdGluZyA8ZW0+dTxcL2VtPiBhbmQgPGVtPnY8XC9lbT4gd2l0aCBhIGRpc3RhbmNlIG9mIDxlbT5kPFwvZW0+LiAoMSAmbGU7IDxlbT51PFwvZW0+LCA8ZW0+djxcL2VtPiAmbGU7IDxlbT5OPFwvZW0+LCAxICZsZTsgPGVtPmQ8XC9lbT4gJmxlOyA1KTxcL3A+XHJcblxyXG48cD5Zb3UgY2FuIGFzc3VtZSB0aGF0IHRoZSBnaXZlbiBncmFwaCBpcyBhIHRyZWUuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIDxlbT5OPFwvZW0+IGxpbmVzLCBwcmludCB0aGUgc3VtIG9mIG1pbmltdW0gZGlzdGFuY2VzIHRvIHRoYXQgdmVydGV4IGZyb20gYWxsIHZlcnRpY2VzLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처