The transportation system of Country C consists of $n$ cities and $m$ bidirectional roads connecting two cities, where the $i$-th ($1 \le i \le m$) road connects cities $u_i$ and $v_i$. Any two cities can reach each other through a sequence of roads.

However, due to a recent major earthquake, all $m$ roads have been destroyed. The cost to repair the $i$-th ($1 \le i \le m$) road is $w_i$. Meanwhile, Country C has $k$ towns prepared for urbanization. For the $j$-th ($1 \le j \le k$) town, the cost of urbanization is $c_j$. After urbanizing the $j$-th ($1 \le j \le k$) town, one can build several roads between this town and the original $n$ cities, where the cost to build a road between it and the $i$-th ($1 \le i \le n$) city is $a_{j,i}$. Country C can choose to urbanize any number of these $k$ towns, or choose not to urbanize any towns at all.

To restore transportation between cities as quickly as possible, the government of Country C hopes to connect all $n$ original cities to each other with the minimum cost, meaning any two original cities can reach each other through a sequence of repaired or newly built roads. You need to help them find the minimum cost to connect all $n$ original cities.

Input

The first line contains three non-negative integers $n, m, k$, representing the number of original cities, the number of roads, and the number of towns prepared for urbanization, respectively.

The $i+1$-th ($1 \le i \le m$) line contains three non-negative integers $u_i, v_i, w_i$, representing the two cities connected by the $i$-th road and the cost to repair that road.

The $j+m+1$-th ($1 \le j \le k$) line contains $n+1$ non-negative integers $c_j, a_{j,1}, a_{j,2}, \dots, a_{j,n}$, representing the cost to urbanize the $j$-th town and the costs to build roads between that town and each of the original cities.

Output

Output a single non-negative integer representing the minimum cost to connect all $n$ original cities.

Examples

Input 1

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

Output 1

13

Note 1

The government of Country C can choose to repair the 3rd and 4th roads, then urbanize the 1st town and build roads between it and the 1st and 3rd cities. The total cost is $5 + 4 + 1 + 1 + 2 = 13$. It can be proven that no cost smaller than 13 can connect the 4 original cities.

Examples 2, 3, 4

See the files road/road2.in and road/road2.ans, road/road3.in and road/road3.ans, and road/road4.in and road/road4.ans in the contestant directory. These examples satisfy the constraints of test cases 11-12, 13-14, and 15-16, respectively.

Constraints

For all test data, it is guaranteed that: $1 \le n \le 10^4$, $1 \le m \le 10^6$, $0 \le k \le 10$; For all $1 \le i \le m$, $1 \le u_i, v_i \le n$, $u_i \neq v_i$, and $0 \le w_i \le 10^9$; For all $1 \le j \le k$, $0 \le c_j \le 10^9$; For all $1 \le j \le k$ and $1 \le i \le n$, $0 \le a_{j,i} \le 10^9$; * Any two original cities can reach each other through a sequence of original roads.

Special Property A: For all $1 \le j \le k$, $c_j = 0$ and there exists at least one $1 \le i \le n$ such that $a_{j,i} = 0$.