Chia nhóm

Một công ty có $n$ nhân viên, các nhân viên được đánh số từ $1$ đến $n$. 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 $i$ không muốn cùng nhóm với nhân viên $p_i$ $(1\le i\le 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 $i$ khác nhóm với nhân viên $p_i$. 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 $i$ cùng nhóm với nhân viên $p_i$ là $w_i$.

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\le k\le m)$ là có thêm cặp nhân viên $(u_k,v_k)$ không muốn cùng nhóm với nhau và nếu muốn cả hai nhân viên $u_k$ và $v_k$ đồng ý cùng nhóm thì phải mất thời gian thuyết phục cặp $(u_k,v_k)$ là $t_k$.

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

• Dòng đầu chứa số nguyên dương $n$ $(n\le {10}^5)$;
• Dòng thứ $i$ trong số $n$ dòng tiếp theo chứa hai số nguyên dương $p_i,w_i$ $(p_i\le n;p_i\ne i;w_i\le {10}^9)$;
• Dòng tiếp theo chứa số nguyên không âm $m$ $(m\le {10}^5)$;
• Dòng thứ $k$ trong số $m$ dòng tiếp theo chứa ba số nguyên dương $u_k,v_k,t_k$ $(u_k,v_k\le n;u_k\ne v_k;u_k\ne p_{v_k};v_k\ne p_{u_k};t_k\le {10}^9)$.

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

Dữ liệu ra

In ra $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

• $2\le n\le {10}^5$; $0\le m\le {10}^5$.
• $1\le p_i\le n$, $p_i\ne i$; $1\le w_i\le {10}^9$.
• $1\le u_k,v_k\le n$; $u_k\ne v_k$; $u_k\ne p_{v_k}$; $v_k\ne p_{u_k}$; $1\le t_k\le {10}^9$.

Subtasks

• Subtask 1 ($20\%$ số điểm): $m=0$, $n\le 1000$ và dãy $p_1,p_2,\dots ,p_n$ là hoán vị của $1,2,\dots ,n$.
• Subtask 2 ($20\%$ số điểm): $m=0$, $n\le 1000$.
• Subtask 3 ($25\%$ số điểm): $m\le 1000$, $n\le 1000$.
• Subtask 4 ($15\%$ số điểm): dãy $p_1,p_2,\dots ,p_n$ là hoán vị của $1,2,\dots ,n$.
• Subtask 5 ($20\%$ số điểm): không có ràng buộc gì thêm.

Ví dụ