Công ty của HN có N nhân viên, nhân viên thứ i có một năng lực làm việc được đánh giá bằng một số nguyên là q_i.

HN muốn tổ chức lại công ty của mình theo quy tắc người u là cấp trên của người v khi q_u > q_v. HN đã lên một danh sách gồm M dòng, mỗi dòng thể hiện bởi 3 giá trị là u, v, c thể hiện: nếu u trở thành cấp trên của v thì lương tổng lương phải trả cho 2 anh này là c, tất nhiên q_u > q_v.

HN nhờ bạn xây dựng lại công ty mình sao cho tổng lương phải trả cho các nhân viên là ít nhất. Lưu ý rẳng, công ty chỉ có duy nhất một sếp tổng, tức là nhân viên viên mà không có ai là cấp trên của anh ta.

Dữ liệu vào:

- Dòng 1 chứa giá trị N (1 ≤ N ≤ 1000)

- Dòng 2 chứa N giá trị là q₁, q₂, …, q_N (0 ≤ q_i ≤ 10⁶)

- Dòng 3 chứa M (0 ≤ M ≤ 10000)

- M dòng tiếp theo, mỗi dòng chứa 3 số nguyên u, v, c (0 ≤ c ≤ 10⁶, q[u] > q[v])

Kết quả ra:

- Tổng lương thấp nhất phải trả cho các nhân viên, trong trường hợp không thể tổ chức lại được thì ghi ra -1.