Tổng khoảng cách trên cây

Một cây trong lý thuyết đồ thị là một đồ thị vô hướng, có trọng số, liên thông và không chứa chu trình. Một cây gồm $N$ đỉnh sẽ có đúng $N-1$ cạnh.

Yêu cầu: Cho một cây $N$ đỉnh, bạn hãy tính tổng khoảng cách từ mỗi đỉnh đến tất cả các đỉnh còn lại. Cụ thể, với mỗi đỉnh $u$ ($1 \le u \le N$), bạn phải tính:
\begincenter
$
S_u = \sum_{v=1}^{N} \text{dist}(u, v)
$
\endcenter
trong đó $\text{dist}(u, v)$ là độ dài đường đi ngắn nhất từ $u$ đến $v$ trên cây (tổng trọng số các cạnh trên đường đi).

Input

Dòng đầu tiên chứa một số nguyên dương $N$ ($1 \le N \le 10^5$) --- số đỉnh của cây.
$N-1$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u, v, w$ ($1 \le u, v \le N$, $u \ne v$, $1 \le w \le 10^6$) --- mô tả một cạnh nối hai đỉnh $u$ và $v$ với trọng số $w$.

Dữ liệu đảm bảo đồ thị nhận được là một cây.

Output

Gồm $N$ dòng, dòng thứ $i$ chứa một số nguyên là tổng khoảng cách từ đỉnh $i$ đến tất cả các đỉnh còn lại.

Example

Test 1

Input

Output

Note

Trong ví dụ trên:

Từ đỉnh 1: khoảng cách đến 2 là 13, đến 3 là 18, đến 4 là 7. Tổng: $13 + 18 + 7 = 38$
Từ đỉnh 2: khoảng cách đến 1 là 13, đến 3 là 5, đến 4 là 6. Tổng: $13 + 5 + 6 = 24$
Từ đỉnh 3: khoảng cách đến 1 là 18, đến 2 là 5, đến 4 là 11. Tổng: $18 + 5 + 11 = 34$
Từ đỉnh 4: khoảng cách đến 1 là 7, đến 2 là 6, đến 3 là 11. Tổng: $7 + 6 + 11 = 24$

Scoring

Subtask 1 (40 điểm): $N \le 1000$
Subtask 2 (60 điểm): Không có ràng buộc gì thêm

Điều hướng chính

Ngôn ngữ

Phím tắt

Input

Output

Example

Scoring

Bình luận