Best Dispatch Hub

Uber operates in a city whose road network forms a tree. There are N intersections numbered 0 through N-1 and exactly N-1 bidirectional roads. Every intersection is reachable from every other intersection. Each road connects intersections u and v and has a positive travel time w. If a driver dispatch hub is placed at intersection r, its dispatch cost is the sum of the shortest travel times from r to all N intersections, including a travel time of 0 from r to itself. For every possible hub location r, compute its dispatch cost. Input format: - First line: N - Next N-1 lines: three integers u, v, and w describing a bidirectional road Print N space-separated integers. The value at index r must be the dispatch cost when the hub is placed at intersection r. Use 64-bit arithmetic.

1 <= N <= 5 * 10^4
0 <= u, v < N
1 <= w <= 10^6

4
0 1 1
0 2 1
2 3 1

4 6 4 6

2
0 1 7

7 7