Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.

Chef has a collection of N postage stamps. Each stamp belongs to some type, which are enumerated as positive integers. More valuable stamps have a higher enumerated type. So, type 1 is the least valuable type of stamps, type 2 is a bit more valuable, and so on.
Chef often communicates with other philatelists via a stamp exchange website called P-bay. On any particular day, P-bay lists several offers, each of which is represented as an unordered pair {A, B}, allowing its users to exchange stamps of type A with an equal number of stamps of type B. Chef can use such an offer to put up any number of stamps of enumerated type A on the website and get the same number of stamps of type B in return, or vice-versa (of course, he must have enough stamps of the corresponding type). Assume that any number of stamps Chef wants are always available on the site's exchange market. Each offer is open during only one day: Chef can't use it after this day, but he can use it several times during this day. If there are some offers which are active during a given day, Chef can use them in any order.
Chef is interested in making his collection as valuable as possible. Help him to find maximum possible value of his collection after going through (accepting or declining) all the offers. Value of Chef's collection is equal to the sum of type enumerations of all stamps in the collection.

------ Input ------

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two integers N and M denoting number of stamps in Chef's collection and number of offers, respectively.
Next line contains N integers denoting the enumerated types of stamps in Chef's collection.
The i^{th} of the following M lines contains three integers — T_{i}, A_{i} and B_{i} — denoting that on day T_{i}, there is an offer about exchanging stamps of types A_{i} and B_{i}.

------ Output ------

For each test case, output a single line containing maximum possible value of Chef's collection after all offers.

------ Constraints ------

$1 ≤ T ≤ 10$
$1 ≤ N ≤ 2*10^{5}$
$1 ≤ M ≤ 5*10^{4}$
$Types are enumerated with integers from 1 to 5*10^{4}$
$1 ≤ T_{i} ≤ 5*10^{4}$

------ Subtasks ------

Subtask 1: (33 points)

$1 ≤ M ≤ 1000$
$Types are enumerated with integers from 1 to 1000$
$1 ≤ T_{i} ≤ 1000$

Subtask 2: (67 points)

$Original constraints$

----- Sample Input 1 ------
1

3 4

1 3 5

1 4 3

1 1 3

2 6 22

3 5 8
----- Sample Output 1 ------
16
----- explanation 1 ------
Example case 1. Chef can use 2nd offer to exchange the stamp of type 1 with an stamp of type 3. After that he can use 1st offer to exchange his 2 stamps of type 3 with 2 stamps of type 4. Finally, on 3rd day Chef uses the offer to exchange the stamp of type 5 with an stamp of type 8. After this transaction, value of his collection becomes 4 + 4 + 8 = 16.

见题面

见题面