Tom is visiting the country Hackerland. Hackerland has n cities and m bi-directional roads. There are k types of tokens. Token i costs \(c_i \). The costs of the tokens are such that for all \(2 \le i \le k\), \( c_i \ge 2 c_{i - 1} \). For each road, you need to have a particular set of tokens, if you want to travel it. Note that you don't have to give the tokens, you just need to show them. Thus, one token can be used at any number of roads, where it is required. Tom wants to select a set of tokens, such that using them, he can go from any city to any other city. You have to help him minimize the total cost of tokens he buys.

Input:

• The first line contains three space separated integers, n m and k .
• The second line contains k space separated integers, where the \(i^{\text{th}} \) integer denotes the price of \(i^{\text{th}} \) token, i.e. \(c_i\) .
• \(i^{\text{th}} \) of the next m lines contains three integers \(u_i, v_i, l_i\), where \(l_i\) is the number of tokens required by the \(i^{\text{th}} \) road, followed by \(l_i\) indices denoting the tokens required. This road connects cities \(u_i\) and \(v_i\)

Output:

• Print one integer containing the minimum cost of tokens Tom has to buy, such that he can travel from any city to any other city. If it is impossible to choose such a set of tokens, print 1.

Constraints

• \(1 \le n \le 10^5 \)

• \( 1 \le m \le 10^5 \)

• No road connects a city to the same city. However, there can be multiple roads between two cities.

• \( 1 \le c_i \le 10^{18} \)

• For all \(2 \le i \le k \), \(c_i \ge 2 c_{i - 1} \)