Chào mừng bạn đến với thế giới "Tóp Tóp Showbiz" - nơi mà drama hít mãi không hết, "phốt" chồng "phốt" như ruộng bậc thang. Trong thế giới này, có ~n~ Chiến thần Review (được đánh số từ ~1~ đến ~n~). Các chiến thần này có mối quan hệ dây mơ rễ má với nhau tạo thành một cấu trúc cây (nghĩa là sơ đồ quan hệ của họ liên thông và không có vòng lặp, vì drama mà đi vòng tròn thì chán lắm).

Mỗi chiến thần ban đầu thuộc về một "hệ tư tưởng" khác nhau. Có người hệ "Bún đậu mắm tôm", người hệ "Bún đậu nước tương", người thì hệ "Flexing đến hơi thở cuối cùng",... Hệ tư tưởng của người thứ ~i~ là một số nguyên ~a[i]~.

Giữa các chiến thần có các đường dây "liên lạc ngầm". Mỗi đường dây kết nối giữa hai chiến thần ~u[i]~ và ~v[i]~ có một "chỉ số va chạm" là ~c[i]~. Luật chơi của Drama Showbiz như sau:

• Nếu hai chiến thần ~u~ và ~v~ có đường dây liên lạc và cùng hệ tư tưởng: Họ sẽ "xin vía" nhau, livestream tung hứng, thả tim kịch liệt ~\Rightarrow~ Hòa bình, thiệt hại là ~0~.

• Nếu hai chiến thần ~u~ và ~v~ có đường dây liên lạc nhưng khác hệ tư tưởng: Họ sẽ "combat" cực căng, check VAR từng milimét, lên bài bóc phốt ~\Rightarrow~ Gây ra thiệt hại đúng bằng chỉ số va chạm ~c[i]~.

Bạn là "Trùm Cuối Media". Bạn có quyền năng tối thượng: ~q~ lần thực hiện phép thuật "Tẩy não". Mỗi lần, bạn bắt ép một chiến thần ~v~ phải "quay xe" chuyển sang hệ tư tưởng ~x~.

Nhiệm vụ: Sau mỗi lần một chiến thần "quay xe", hãy tính tổng thiệt hại của toàn bộ cái Showbiz này.

Input

• Dòng đầu tiên: hai số nguyên ~n~ và ~q~ ~(1 \le n, q \le 10^5)~ - số lượng chiến thần và số lần bạn đổi hệ tư tưởng.

• Dòng thứ hai: ~n~ số nguyên ~a[1], a[2], \dots, a[n]~ ~(1 \le a[i] \le n)~ - Hệ tư tưởng ban đầu của các chiến thần.

• ~n-1~ dòng tiếp theo: mỗi dòng chứa ~3~ số ~u, v, c~ ~(1 \le u, v \le n, 1 \le c \le 10^9)~ - mô tả đường dây liên lạc giữa chiến thần ~u~ và ~v~ với chỉ số va chạm ~c~.

• ~q~ dòng tiếp theo: mỗi dòng chứa ~2~ số ~v~ và ~x~ ~(1 \le v, x \le n)~ - yêu cầu chiến thần ~v~ đổi sang hệ tư tưởng ~x~.

Ghi chú: Tổng ~n~ và tổng ~q~ trên tất cả các test case không vượt quá ~2 \cdot 10^5~.

Output

• Với mỗi truy vấn, in ra một số nguyên duy nhất trên một dòng: Tổng thiệt hại của toàn bộ Showbiz sau khi chiến thần "quay xe".

Scoring

Sample Input 1

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

Sample Output 1

12
5
0
12