A7864 | Hierarchy

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.