Hệ thống cấp bậc

Một công ty có $n$ nhân viên. Cần xây dựng một cây cấp bậc kiểu "cấp trên – cấp dưới": mỗi nhân viên, ngoại trừ đúng một người (người đứng đầu), có đúng một cấp trên.

Có $m$ đơn đăng ký, mỗi đơn có dạng: "nhân viên $a_i$ sẵn sàng làm cấp trên của nhân viên $b_i$ với chi phí phụ trội $c_i$". Mỗi nhân viên $j$ có một chỉ số năng lực $q_j$ đã biết, và mọi đơn đều thoả mãn $q_{a_i}>q_{b_i}$.

Hãy tính tổng chi phí nhỏ nhất để xây dựng cây cấp bậc như vậy, hoặc khẳng định không thể.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ — số nhân viên.
• Dòng thứ hai chứa $n$ số nguyên $q_1,q_2,\dots ,q_n$ — năng lực của các nhân viên.
• Dòng thứ ba chứa số nguyên $m$ — số đơn đăng ký.
• $m$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $a_i$, $b_i$, $c_i$ — đơn đăng ký. Hai đơn khác nhau có thể trùng cặp $(a,b)$ nhưng khác $c$.

Dữ liệu ra

In ra một số nguyên duy nhất — tổng chi phí nhỏ nhất để xây cây cấp bậc, hoặc $-1$ nếu không thể.

Ràng buộc

• $1\le n\le 1000$
• $0\le q_j\le {10}^6$
• $0\le m\le 10000$
• $1\le a_i,b_i\le n$, $0\le c_i\le {10}^6$
• $q_{a_i}>q_{b_i}$ với mọi đơn $i$.

Ví dụ