시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1.5 초 128 MB 72 28 22 37.931%

문제

로스팅하는 엠마는 바리스타입니다. 엠마는 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+XHVjNWUwXHViOWM4XHViMjk0IFx1ZDU1YyBcdWFjMWNcdWM3NTggXHViMThkXHVjN2E1XHVjNzQ0IFx1YzgxNVx1ZDU3NCBcdWIxOGRcdWM3YTUgXHVjNjA2XHVjNWQwIFx1Yjg1Y1x1YzJhNFx1ZDMwNSBcdWMyZGNcdWMxMjRcdWM3NDQgXHViOWM4XHViODI4XHVkNTU4XHViODI0XHVhY2UwIFx1ZDU2OVx1YjJjOFx1YjJlNC4gXHVjNzc0IFx1YjU0YywgXHViMmU0XHViOTc4IFx1YjE4ZFx1YzdhNVx1YzVkMFx1YzExYyBcdWI4NWNcdWMyYTRcdWQzMDUgXHVjMmRjXHVjMTI0XHVhZTRjXHVjOWMwXHVjNzU4IFx1YWM3MFx1YjlhY1x1Yzc1OCBcdWQ1NjlcdWI0ZTRcdWM3NDQgXHVjNTRjXHVjNTQ0XHVjNTdjLCBcdWQ2YThcdWM3MjhcdWM4MDFcdWM3M2NcdWI4NWMgXHViODVjXHVjMmE0XHVkMzA1IFx1YzJkY1x1YzEyNFx1Yzc1OCBcdWM3MDRcdWNlNThcdWI5N2MgXHVjODE1XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWM3NDQgXHVhYzgzXHVjNzg1XHViMmM4XHViMmU0LiBcdWFkZjhcdWI3ZWNcdWJiYzBcdWI4NWMgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YjE4ZFx1YzdhNVx1YjljOFx1YjJlNCBcdWIyZTRcdWI5NzggXHViMThkXHVjN2E1XHViNGU0XHVjNWQwXHVjMTFjIFx1YWRmOCBcdWIxOGRcdWM3YTVcdWM3M2NcdWI4NWMgXHVhYzAwXHViMjk0IFx1Y2Q1Y1x1YjJlOCBcdWFjNzBcdWI5YWNcdWI0ZTRcdWM3NTggXHVkNTY5XHVjNzQ0IFx1YWQ2Y1x1ZDU3NFx1YzkwZFx1YzJkY1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgPGVtPk48XC9lbT5cdWM3NzQgXHVjNzg1XHViODI1XHViNDI5XHViMmM4XHViMmU0LiZuYnNwOygxJnRoaW5zcDsmbGU7JnRoaW5zcDs8ZW0+TjxcL2VtPiZ0aGluc3A7JmxlOyZ0aGluc3A7MyZ0aGluc3A7JnRpbWVzOyZ0aGluc3A7MTA8c3VwPjU8XC9zdXA+KTxcL3A+XHJcblxyXG48cD48ZW0+TjxcL2VtPi0xIFx1YzkwNCBcdWIzZDlcdWM1NDggXHVjMTM4IFx1YzIxOCA8ZW0+dTxcL2VtPiwgPGVtPnY8XC9lbT4gXHVjNjQwIDxlbT5kPFwvZW0+XHVhYzAwIFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC4gXHVjNzc0XHViMjk0IDxlbT51PFwvZW0+XHViYzg4XHVjOWY4IFx1YjE4ZFx1YzdhNVx1YWNmYyA8ZW0+djxcL2VtPlx1YmM4OFx1YzlmOCBcdWIxOGRcdWM3YTVcdWM3NDAgXHVjMTFjXHViODVjIFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YWRmOCBcdWFjNzBcdWI5YWNcdWIyOTQgPGVtPmQ8XC9lbT5cdWM3ODRcdWM3NDQgXHViNzNiXHVkNTY5XHViMmM4XHViMmU0LiZuYnNwOygxJnRoaW5zcDsmbGU7JnRoaW5zcDs8ZW0+dTxcL2VtPiwmdGhpbnNwOzxlbT52PFwvZW0+JnRoaW5zcDsmbGU7JnRoaW5zcDs8ZW0+TjxcL2VtPiwmdGhpbnNwOzEmdGhpbnNwOyZsZTsmdGhpbnNwOzxlbT5kPFwvZW0+JnRoaW5zcDsmbGU7JnRoaW5zcDs1KTxcL3A+XHJcblxyXG48cD5cdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHVhZGY4XHViNzk4XHVkNTA0XHViMjk0IFx1ZDJiOFx1YjlhY1x1Yzc4NVx1YjJjOFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD48ZW0+TjxcL2VtPlx1YWMxY1x1Yzc1OCBcdWM5MDQgXHViM2Q5XHVjNTQ4IFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWIxOGRcdWM3YTVcdWM1ZDAgXHViMzAwXHVkNTc0IFx1YjJlNFx1Yjk3OCBcdWIxOGRcdWM3YTVcdWI0ZTRcdWM1ZDBcdWMxMWMgXHVhZGY4IFx1YjE4ZFx1YzdhNVx1YzczY1x1Yjg1YyBcdWFjMDBcdWIyOTQgXHVjZDVjXHViMmU4IFx1YWM3MFx1YjlhY1x1YjRlNFx1Yzc1OCBcdWQ1NjlcdWM3NDQgXHVjZDljXHViODI1XHVkNTY5XHViMmM4XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjE1NjQ3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVHJlZSBhbmQgUGF0aCIsImRlc2NyaXB0aW9uIjoiPHA+QSB0cmVlIHdpdGggPGVtPk48XC9lbT4gdmVydGljZXMgMSB0byA8ZW0+TjxcL2VtPiBpcyBnaXZlbi4gQWxsIHRoZSBlZGdlcyBoYXZlIGEgZGlzdGFuY2Ugd2hpY2ggaXMgYXQgbGVhc3QgMS4gRm9yIGV2ZXJ5IHZlcnRleCwgY2FsY3VsYXRlIHRoZSBzdW0gb2YgbWluaW11bSBkaXN0YW5jZXMgdG8gdGhhdCB2ZXJ0ZXggZnJvbSBhbGwgdmVydGljZXMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD48ZW0+TjxcL2VtPiBpcyBnaXZlbiBpbiB0aGUgZmlyc3QgbGluZS4gKDEgJmxlOyA8ZW0+TjxcL2VtPiAmbGU7IDMgJnRpbWVzOyAxMDxzdXA+NTxcL3N1cD4pPFwvcD5cclxuXHJcbjxwPkZvciB0aGUgbmV4dCA8ZW0+TjxcL2VtPi0xIGxpbmVzLCB0aHJlZSBudW1iZXJzIDxlbT51PFwvZW0+IGFuZCA8ZW0+djxcL2VtPiBhbmQgPGVtPmQ8XC9lbT4gaXMgZ2l2ZW4uIFRoaXMgbWVhbnMgdGhhdCB0aGVyZSBpcyBhbiBlZGdlIGNvbm5lY3RpbmcgPGVtPnU8XC9lbT4gYW5kIDxlbT52PFwvZW0+IHdpdGggYSBkaXN0YW5jZSBvZiA8ZW0+ZDxcL2VtPi4gKDEgJmxlOyA8ZW0+dTxcL2VtPiwgPGVtPnY8XC9lbT4gJmxlOyA8ZW0+TjxcL2VtPiwgMSAmbGU7IDxlbT5kPFwvZW0+ICZsZTsgNSk8XC9wPlxyXG5cclxuPHA+WW91IGNhbiBhc3N1bWUgdGhhdCB0aGUgZ2l2ZW4gZ3JhcGggaXMgYSB0cmVlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciA8ZW0+TjxcL2VtPiBsaW5lcywgcHJpbnQgdGhlIHN1bSBvZiBtaW5pbXVtIGRpc3RhbmNlcyB0byB0aGF0IHZlcnRleCBmcm9tIGFsbCB2ZXJ0aWNlcy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처