尼克的公司雇用了 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。