题目描述

小 $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

样例输入 #1

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

样例输出 #1

11

样例 #2

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