Một công ty có n nhân viên, các nhần viên được đánh số tử 1 đến r. Công ty đang chuẩn bị kỉ niệm 100 năm thành lập và dự định tổ chức nhiều hoạt động ngoại khóa. Một hoạt động được nhiều người mong đọi đòi hỏi phải chia n nhân viên thành hai nhóm. Qua thu thập thông tin, Ban tổ chức biết được rắng, nhân viên 1 không muốn cùng nhóm với nhân viên pi (1 <= i <= n). Dựa trên yêu cầu của mỗi nhân viên, Ban tổ chức muốn tìm một cách chia n nhân viên thành hai nhóm mà nhân viên (khác nhóm với nhân viên pi. Trường hợp không tồn tại cách chia thóa mắn, Ban tổ chức sẽ phải thuyết phục một số người chấp nhận cùng nhóm với người mà họ không muốn, thời gian để thuyết phục nhân viên ỉ cùng nhóm với nhân viên pi là wi.

Theo thông tin mà Ban tổ chức mới nhận được thì dỡ liệu thu thập có thể chưa đầy đủ, có thể có thêm một cặp nhân viên (u, v) không muốn cùng một nhóm. Ban tố chức đã đưa ra một danh sách gồm m + 1 giá định: Giá định 0, không có thêm cặp nào; giá định thứ k (1 ≤ k <= m) là có thêm cặp nhân viên (uk, vk) không muốn cùng nhóm với nhau và nếu muốn cà hai nhân viên uk và vk đồng ý cùng nhóm thì phải mất thời gian thuyết phục cặp (ux, vk) là tk.

Yêu cầu: Với mỗi già định, hãy giúp Ban tổ chức tính toán tổng thời gian thuyết phục ít nhất để có thể chia n nhân viên thành hai nhóm.

Dữ liệu: Vào từ file văn bản TEAMUP.INP:

• Dòng đầu chứa số nguyên dương n (n ≤ 10^5);

• Dòng thứ i trong số n dòng tiếp theo chứa hai số nguyên dương pi, wi (pi <= n, pi khác i, wi <= 10^9);

• Dòng tiếp theo chứa số nguyên không âm m (m ≤ 10^5);

• Dòng thứ k trong số m dòng tiếp theo chứa ba số nguyên dương uk, vk, tk (uk, vk <= n; uk khác vk; uk khác Pvk; vk khác Puk; tk <= 10^9).

Các số trên cùng một dòng cách nhau bởi đấu cách.

Kết quả: Ghi ra file văn bản TEAMUP.OUT gồm m + 1 dòng, mỗi dòng một số nguyên là tổng thời gian thuyết phục ít nhất lần lượt tương ứng cho từng giả định.

Ràng buộc:

• Có 20% số test ứng với 20% số điểm của bài thóa mãn: m = 0,n ≤ 1000 và dãy Pi, P2....Pn là một hoán vị của 1,2, .., n;

• 20% số test khác ứng với 20% số điểm của bài thoa mãn: m = 0 vàn ≤ 1000;

• 25% số test khác ứng với 25% số điểm của bài thóa mãn: m ≤ 1000 và n ≤ 1000;

• 15% số test khác ứng với 15% số điểm của bải thoa mãn: dãy P1, P2 .., Pn là một hoán vị của 1,2, .., п;

• 20% số test còn lại ứng với 20% số điểm của bải không có ràng buộc gì thêm.

Input:

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

Output:

1
2
2

Giải thích:

• Giá định 0: Thuyết phục nhân viên 3 mất 1 đơn vị thời gian. Khi đó, có thể chia thành hai nhóm (1,3,4) và (2,5)

• Giá định 1: Thuyết phục nhân viên 5 mất 2 đơn vị thời gian. Khi đó, có thể chia thành hai nhóm (1,3,5) và (2,4)

• Giá định 2: Thuyết phục nhân viên 3 mất 1 đơn vị thời gian và thuyết phục cặp (1,3) mất 1 đơn vị thời gian. Khi đó, có thể chia thành hai nhóm (1,3,4) và (2,5)