← 返回题目列表

Codeforces · 17/B

B. 层次结构

中文机器翻译题面 查看原题

尼克的公司雇用了 n 名员工。现在Nick需要在公司中建立一个“主管-从属”关系的树形层次结构(也就是说,除了一名员工外,每个员工都只有一位主管)。有 m 个申请,格式如下:“员工 ai 准备以额外费用 ci 成为员工 bi 的主管”。每个员工的资格 qj 已知,并且对于每个应用程序,以下条件成立:qai > qbi。

你能帮尼克计算一下这样一个层次结构的最低成本吗?或者发现不可能建立它。

输入

第一输入行包含整数 n (1 ≤ n ≤ 1000) — 公司员工数量。下面一行包含 n 个空格分隔的数字 qj (0 ≤ qj ≤ 106)——员工的资质。以下行包含数字 m (0 ≤ m ≤ 10000) — 收到的申请数量。以下 m 行包含应用程序本身,每个应用程序均采用三个空格分隔的数字的形式:ai、bi 和 ci (1 ≤ ai, bi ≤ n, 0 ≤ ci ≤ 106)。不同的申请可以是相似的,即它们可以来自同一名员工,他提出成为同一个人的主管,但成本不同。对于每个应用程序 qai > qbi。

输出

输出唯一的一行 — 构建此类层次结构的最低成本,如果无法构建,则输出 -1。

示例

输入 #1

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

输出 #1

11

输入 #2

3
1 2 3
2
3 1 2
3 1 3

输出 #2

-1

注意

在第一个示例中,构建层次结构的可能方法之一是采用索引为 1、2 和 4 的应用程序,其中 11 为最小总成本。在第二个示例中,不可能构建所需的层次结构,因此答案为 -1。