Cộng đường đi trên cây

Cho một cây có $N$ đỉnh đánh số từ $1$ đến $N$, gốc tại đỉnh $1$. Ban đầu giá trị tại mỗi đỉnh bằng $0$.

Có $Q$ thao tác, mỗi thao tác có dạng $(u,v,w)$: cộng $w$ vào giá trị của mọi đỉnh nằm trên đường đi đơn từ $u$ đến $v$ (bao gồm cả $u$ và $v$).

Sau khi thực hiện đủ $Q$ thao tác, hãy in ra giá trị cuối của từng đỉnh.

Dữ liệu vào

• Dòng 1: hai số nguyên $N$ và $Q$.
• $N-1$ dòng tiếp theo: mỗi dòng hai số nguyên $a$ và $b$ ($1\le a,b\le N$, $a\ne b$) mô tả một cạnh nối hai đỉnh $a$ và $b$.
• $Q$ dòng tiếp theo: mỗi dòng ba số nguyên $u$, $v$, $w$ mô tả một thao tác.

Dữ liệu ra

Một dòng gồm $N$ số nguyên cách nhau bởi dấu cách: giá trị cuối của đỉnh $1,2,\dots ,N$.

Ràng buộc

• $1\le N,Q\le 2·{10}^5$
• $1\le u,v\le N$
• $1\le w\le {10}^9$
• Cho phép $u=v$ (đường đi chỉ chứa một đỉnh).

Ví dụ

Ghi chú

• Đáp số tại mỗi đỉnh có thể lớn (tới khoảng $2·{10}^{14}$), hãy dùng kiểu số nguyên 64-bit.