Roasting Emma is a barista too

Interview

Time limit1.5sMemory limit128 MB

Summary

Given a weighted tree, compute for every vertex the sum of shortest distances to all other vertices.

Level: Medium5 of 10
Topics: Tree, DFS, Dynamic programming, Prefix sum
Solved: No attempts yet

Problem

Emma roasts coffee beans and works as a barista. She has linked her farms into a tree with $N$ vertices, and the farms are numbered 1 through $N$ . Each edge means you can travel between those two farms, and the weight of an edge is the travel distance.

Emma wants to pick one farm and set up a roasting facility next to it. To place it well she needs to know how far the other farms are from the facility in total. For every farm, find the sum of the shortest distances from all the other farms to that farm.

Input

The first line contains $N$ . ( $1 \le N \le 3 \times 10^5$ )

Each of the next $N-1$ lines contains three integers $u$ , $v$ , and $d$ . Farm $u$ and farm $v$ are connected to each other and the distance between them is $d$ . ( $1 \le u, v \le N$ , $1 \le d \le 5$ )

The given graph is a tree.

Output

Print $N$ lines. Line $i$ contains the sum of the shortest distances from all the other farms to farm $i$ .

Examples4

Example 1

Input

Expected output

Example 2
Input
```
1
```
Expected output
```
0
```
Example 3
Input
```
2
2 1 5
```
Expected output
```
5
5
```
Example 4
Input
```
4
3 4 5
2 3 2
1 2 3
```
Expected output
```
18
12
12
22
```