Cho một cây gồm ~n~ đỉnh, gốc tại đỉnh ~1~. Mỗi đỉnh mang một số, ban đầu bằng ~0~.

Có ~q~ truy vấn, mỗi truy vấn có dạng ~(u, v, w)~ — tăng giá trị của mỗi đỉnh trên đường đi đơn giữa ~u~ và ~v~ thêm ~w~ (tính cả hai đầu mút ~u~ và ~v~).

Hãy tìm giá trị trên mỗi đỉnh sau ~q~ truy vấn.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~.
• ~n - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u~ và ~v~ — có một cạnh nối ~u~ và ~v~.
• ~q~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~u~, ~v~, ~w~ — một truy vấn.

Kết quả

In ra ~n~ số nguyên trên một dòng, cách nhau bởi dấu cách — số thứ ~i~ là giá trị trên đỉnh ~i~.

Ví dụ

Đầu vào:

7 3
1 2
1 3
2 4
2 5
3 6
3 7
1 4 1
5 6 2
6 7 5

Đầu ra:

3 3 7 1 2 7 5

Giải thích: Truy vấn đầu tiên cộng ~1~ vào các đỉnh ~1, 2, 4~. Truy vấn thứ hai cộng ~2~ vào các đỉnh ~5, 2, 1, 3, 6~. Truy vấn thứ ba cộng ~5~ vào các đỉnh ~6, 3, 7~. Chẳng hạn đỉnh ~3~ nhận ~2 + 5 = 7~.

Giới hạn

• ~1 \le n, q \le 10^5~
• ~1 \le u, v \le n~
• ~1 \le w \le 10^9~

Nếu ~u = v~ thì chỉ đỉnh đó được cộng thêm ~w~. Giá trị cuối cùng có thể lên tới ~10^{14}~ nên không vừa trong số nguyên 32 bit.