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}.

提交代码