17B.md (2098B)
1 Source: https://codeforces.com/problemset/problem/17/B 2 3 B. Hierarchy 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 64 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 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**a**i* > *q**b**i*. 22 23 Would you help Nick calculate the minimum cost of such a hierarchy, or find out that it is impossible to build it. 24 25 Input 26 27 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* ≤ 106)— 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* ≤ 106). 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**a**i* > *q**b**i*. 28 29 Output 30 31 Output the only line — the minimum cost of building such a hierarchy, or -1 if it is impossible to build it. 32 33 Examples 34 35 Input 36 37 ``` 38 4 39 7 2 3 1 40 4 41 1 2 5 42 2 4 1 43 3 4 1 44 1 3 5 45 ``` 46 47 Output 48 49 ``` 50 11 51 ``` 52 53 Input 54 55 ``` 56 3 57 1 2 3 58 2 59 3 1 2 60 3 1 3 61 ``` 62 63 Output 64 65 ``` 66 -1 67 ``` 68 69 Note 70 71 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.