Có \(n\) thành phố được kết nối với nhau bởi \(n-1\) con đường, đảm bảo các thành phố liên thông với nhau. Mỗi thành phố \(u\) có một nhà trẻ và có \(a_u\) trẻ em trong đó. An có \(x\) cái kẹo và bắt đầu xuất phát từ thành phố \(s\), di chuyển đến thành phố \(t\) theo đường đi ngắn nhất. Khi An đến một nhà trẻ, An sẽ phát kẹo cho các trẻ em ở đó, An sẽ phát nhiều nhất có thể tại thời điểm đó và các trẻ em tại cùng một nhà trẻ phải được phát cùng số lượng kẹo, tất nhiên có thể sẽ dẫn tới có nhà trẻ mà trẻ em ở đây không nhận được bất kỳ viên kẹo nào. Hãy cho biết khi kết thúc hành trình thì An còn bao nhiêu viên kẹo.

Cho \(q\) truy vấn, mỗi truy vấn tương ứng với bộ ba \((s,t,x)\) hãy đưa ra số kẹo còn lại.

Dữ liệu vào

• Dòng đầu chứa \(n,q\) \((1 \le n,q \le 2 \times 10^5)\)
• \(n-1\) dòng tiếp theo, mỗi dòng chứa hai số \(u,v\) mô tả cạnh nối giữa hai thành phố \(u,v\)
• Dòng tiếp theo chứa \(n\) số \(a_i\) \((1 \le a_i \le 10^9)\)
• \(q\) dòng tiếp theo, mỗi dòng chứa ba số \(s,t,x\) \((1 \le s,t \le n; 1 \le x \le 10^9)\) tương ứng với các truy vấn.

Dữ liệu ra

• Ứng với mỗi truy vấn đưa ra kết quả trên một dòng

Input 1

4 3
1 2
2 3
3 4 
5 2 7 4
1 1 9
2 3 11
3 2 11

Output 1

4
1 
0