Nhóm các bạn học sinh giỏi môn Tin học của tỉnh Gia Lai đã tạo một trò chơi. Hệ thống trò chơi được thiết kế gồm một số con robot và ~N~ trạm được đánh số liên tiếp từ ~1~ tới ~N~. Các trạm được kết nối bởi ~N-1~ đường đi hai chiều, đảm bảo giữa hai trạm bất kì đều tồn tại đường đi. Mỗi trạm được đặt một con số vui vẻ ~L_i~. Mỗi robot mang một con số may mắn ~W~ và một số viên kẹo. Nếu robot mang số may mắn ~W~ đi qua trạm thứ ~i~ có số vui vẻ ~L_i~ mà ~W > L_i~, robot sẽ phải bỏ vào hộp kẹo của trạm ~i~ một lượng kẹo là ~W-L_i~ viên. Nếu robot đi qua có con số may mắn ~W~ không lớn hơn số vui vẻ ~L_i~, robot sẽ được đi qua trạm ~i~ mà không phải mất kẹo. Biết rằng, số viên kẹo mà mỗi robot mang theo luôn đảm bảo để tham gia trò chơi.

Có ~M~ robot chuẩn bị tham gia trò chơi. Robot thứ ~i~ di chuyển từ trạm xuất phát ~S_i~ đến trạm đích ~T_i~ với số may mắn là ~W_i~. Mỗi robot đều đi theo đường đi sao cho khoảng cách di chuyển (số con đường đi qua) phải ít nhất. Tất cả robot đều bị kiểm tra và thu kẹo (nếu có) tại tất cả các trạm nằm trên con đường đi qua, bao gồm trạm xuất phát và trạm đích.

Yêu cầu: Hãy thống kê tổng số kẹo mà mỗi trạm đã thu được sau khi ~M~ robot này hoàn thành trò chơi.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~M~ ~(1 \le N, M \le 3 \times 10^5)~ — số lượng trạm và số lượng robot.

• ~N-1~ dòng tiếp theo: Mỗi dòng chứa hai số nguyên dương ~u_i~ và ~v_i~ ~(1 \le u_i, v_i \le N)~, thể hiện có một đường đi trực tiếp giữa hai trạm này.

• Dòng tiếp theo chứa ~N~ số nguyên ~L_1, L_2, \dots, L_N~ ~(0 \le L_i \le 10^9)~ — số vui vẻ của mỗi trạm.

• ~M~ dòng cuối cùng, mỗi dòng chứa ba số nguyên ~S_i, T_i~ và ~W_i~ ~(1 \le S_i, T_i \le N, 1 \le W_i \le 10^9)~ — thông tin về robot, trạm xuất phát, trạm đích, số may mắn của robot ~i~.

Output

Một dòng duy nhất chứa ~N~ số nguyên (các số cách nhau bởi dấu cách), số thứ ~i~ là tổng số kẹo mà trạm ~i~ đã thu được.

Scoring

Sample Input 1

3 2
1 2
1 3
4 2 6
1 2 5
2 3 9

Sample Output 1

6 10 3

Notes

• Trạm ~1~ thu ~1~ viên trên đường đi ~1 \rightarrow 2~ và ~5~ viên trên đường đi ~2 \rightarrow 1 \rightarrow 3~.

• Trạm ~2~ thu ~3~ viên trên đường đi ~1 \rightarrow 2~ và ~7~ viên trên đường đi ~2 \rightarrow 1 \rightarrow 3~.

• Trạm ~3~ thu ~3~ viên trên đường đi ~2 \rightarrow 1 \rightarrow 3~.