Hierarchy

题意翻译

### 题目描述 小 $n$ 的公司有 $n$ 个员工，每个员工 $i$ 有一个初始的权值 $q_i$ ，每一个员工有且只有一个上司。 有 $m$ 条申请，每个申请由三个数 $a_i$，$b_i$，$c_i$ 构成，代表将 $a_i$ 任命为 $b_i$ 的上司所需要的花费为$c_i$，同时必须保证 $q_{a_i}>q_{b_i}$。试求使每个员工(顶头上司除外)都有且只有一个上司所花费的最小代价。 ### 输入格式 第一行 $n$，第二行 $n$ 个数表示 $q_i$，第三行 $m$，之后 $m$ 行每行三个数表示$a_i$ ，$b_i$，$c_i$。 ### 输出格式 一个整数表示最小代价，若无解则输出 `-1`。 ### 说明/提示 #### 数据规模与约定 $1 \le n \le 10^3$，$0 \le m \le 10^4$, $0 \le q_i \le 10^6$，$0 \le c_i \le 10^6$，$1 \le a_i,b_i \le n$ 。

题目描述

Nick's company employed $ n $ people. Now Nick needs to build a tree hierarchy of «supervisor-surbodinate» relations in the company (this is to say that each employee, except one, has exactly one supervisor). There are $ m $ applications written in the following form: «employee $ a_{i} $ is ready to become a supervisor of employee $ b_{i} $ at extra cost $ c_{i} $ ». The qualification $ q_{j} $ of each employee is known, and for each application the following is true: $ q_{ai}>q_{bi} $ . Would you help Nick calculate the minimum cost of such a hierarchy, or find out that it is impossible to build it.

输入输出格式

输入格式

The first input line contains integer $ n $ ( $ 1<=n<=1000 $ ) — amount of employees in the company. The following line contains $ n $ space-separated numbers $ q_{j} $ ( $ 0<=q_{j}<=10^{6} $ )— the employees' qualifications. The following line contains number $ m $ ( $ 0<=m<=10000 $ ) — amount of received applications. The following $ m $ lines contain the applications themselves, each of them in the form of three space-separated numbers: $ a_{i} $ , $ b_{i} $ and $ c_{i} $ ( $ 1<=a_{i},b_{i}<=n $ , $ 0<=c_{i}<=10^{6} $ ). Different applications can be similar, i.e. they can come from one and the same employee who offered to become a supervisor of the same person but at a different cost. For each application $ q_{ai}>q_{bi} $ .

输出格式

Output the only line — the minimum cost of building such a hierarchy, or -1 if it is impossible to build it.

输入输出样例

输入样例 #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

说明

In the first sample one of the possible ways for building a hierarchy is to take applications with indexes 1, 2 and 4, which give 11 as the minimum total cost. In the second sample it is impossible to build the required hierarchy, so the answer is -1.