AIRPORTS

A team of engineers is designing the public transportation network of the country. Suppose there are ~N~ cities in the country, and initially, there are no railways or airports. The engineers know the cost of constructing airports in ~M~ of these cities. Also, they know the costs of constructing ~K~ railway lines, each of which can connect a pair of cities without passing through any other city.

The goal of the engineers is to connect all cities with each other. Two cities are considered connected if they are connected by a railway (possibly through intermediate cities) or if each of them is connected by railway to another city that has an airport.

Write a program to calculate the minimum cost to connect all cities.

Input

The first line of input contains three natural numbers ~N~, ~M~, and ~K~: the number of cities, the number of possible airports, and the number of possible railway lines.

Each of the next ~M~ lines of input will contain two natural numbers ~i~ and ~A_i~, separated by a space, indicating the cost ~A_i~ of constructing an airport in the ~i~-th city. Assume that the cities are numbered from ~1~ to ~N~, and that for each city, at most one airport cost is provided.

Each of the next ~K~ lines of input will contain three natural numbers ~i~, ~j~, and ~B_{ij}~, separated in pairs by a space, indicating the cost ~B_{ij}~ of constructing a railway line connecting the ~i~-th and ~j~-th cities. Assume that the railway lines operate in both directions, that the numbers ~i~ and ~j~ are different, and that for a pair of cities, at most one railway line cost is provided. Also, assume that if all railway lines are constructed, then every city will be connected to every other city.

Output

The output should consist of a single line containing a single natural number: the minimum cost to connect all cities.

Constraints

~2 \le N \le 10.000~
~0 \le M \le N~
~N-1 \le K \le 500.000~
~1 \le A_i \le 100.000~
~1 \le B_{ij} \le 100.000~
Execution time limit: 1 sec.
Memory limit: 64 MB.

Example of Input - Output:

STDIN (airports.in)

7 2 8
1 5
7 3
1 2 3
1 3 2
6 4 2
3 5 2
5 2 1
5 6 9
6 7 2
2 3 5

STDOUT (airports.out)

17

Explanation of the Example: The minimum cost arises if airports are constructed in cities ~1~ and ~7~, with a cost of ~5 + 3 = 8~, and railway lines between cities ~(1,\;3)~, ~(3,\;5)~, ~(5,\;2)~, ~(6,\;7)~, and ~(6,\;4)~ with a cost of ~2+2+1+2+2=9~, resulting in a total cost of ~8+9=17~.