Thành phố X là một thành phố rộng lớn được chia làm \(n\) phân khu. Các phân khu được nối với nhau bởi \(n - 1\) con đường hai chiều, mỗi con đường nối trực tiếp giữa hai phân khu nào đấy sao cho đảm bảo luôn tồn tại đường đi giữa hai phân khu bất kỳ.

Là thành phố lớn nhất nhì trong cả nước, mật độ phương tiện giao thông ở đây là vô cùng khổng lồ, dẫn đến gánh nặng rất lớn về chi phí bảo trì và sửa chữa và bảo trì cơ sở hạ tầng. Do đó, chính quyền thành phố đã cho xây dựng ở mỗi phân khu một trạm kiểm soát.

Khi một phương tiện giao thông di chuyển tới một phân khu, phương tiện bắt buộc phải đi qua trạm kiểm soát này. Mỗi trạm kiểm soát sẽ có một mức giới hạn tải trọng, trạm kiểm soát ở phân khu \(i\) sẽ có mức giới hạn là \(l_{i}\) kg. Giả sử một phương tiện đi qua và có tải trọng lớn hơn giới hạn tải trọng của trạm kiểm soát, chủ phương tiện phải trả cho trạm kiểm soát đó khoảng phạt là \(1\) đồng cho mỗi kg vượt giới hạn. Cụ thể hơn, nếu một phương tiện có tải trọng \(w\) đi qua trạm kiểm soát ở phân khu \(i\), chủ phương tiện đó phải trả cho trạm kiểm soát đó \(\max(w - l_{i}, 0)\) đồng.

Bạn biết được ngày hôm nay đã có \(m\) phương tiện di chuyển, phương tiện \(i\) di chuyển từ phân khu \(s_{i}\) tới phân khu \(t_{i}\) với trọng tải \(w_{i}\) (Lưu ý rằng phương tiện cũng phải đi qua trạm kiểm soát của điểm xuất phát và đích đến). Với mỗi trạm kiểm soát, hãy cho biết sau ngày hôm nay trạm kiểm soát đó đã thu được bao nhiêu tiền.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) \((1 \leq n, m \leq 3 \times 10^{5})\).
• Trong \(n - 1\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(u_{i}\) và \(v_{i}\) \((1 \leq u_{i}, v_{i} \leq n)\) có nghĩa là có đường nối trực tiếp giữa phân khu \(u_{i}\) và \(v_{i}\).
• Dòng tiếp theo chứa \(n\) số nguyên \(l_{i}\) \((0 \leq l_{i} \leq 10^{9})\).
• Trong \(m\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(s_{i}, t_{i}\) và \(w_{i}\) \((1 \leq s_{i}, t_{i} \leq n, 1 \leq w_{i} \leq 10^{9})\).

Output

• Một dòng duy nhất chứa \(n\) số nguyên, số thứ \(i\) là số tiền mà trạm kiểm soát ở phân khu \(i\) thu được sau ngày hôm nay.

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(n, m \leq 100\).
• Subtask \(2\) (\(25\%\) số điểm): Thành phố có dạng đường thẳng.
• Subtask \(3\) (\(25\%\) số điểm): \(l_{i} = 0\) với mọi \(1 \leq i \leq n\).
• Subtask \(4\) (\(25\%\) số điểm): Không có ràng buộc gì thêm.

Example

4 1
1 2
2 3
3 4
1 2 3 4
1 4 3       

2 1 0 0 

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

0 5 7 5 0 5 2 2