407558: GYM102829 E Buying Tacos

Kevin is trying to buy tacos for an upcoming UTPC contest! Since the club's budget is limited, he wants to spend the least possible money while also feeding all the attendees comfortably. Normally, this would simply entail going to Torchy's Tacos and buying the appropriate distribution of tacos, but today, Kevin has found a way to reduce the cost.

It turns out that there's a taco market right outside Torchy's! Lots of people have gathered around and are willing to make some trades. Specifically, for some tacos $$$i, j$$$, if you have one of taco $$$i$$$, you can exchange it for taco $$$j$$$ for a price $$$p_{i, j}$$$. While these trades may not be possible for all pairs of tacos, nor are they bidirectional, for the trades that do exist, you can do them an infinite amount of times.

Given the base prices of all the tacos as well as the prices of all these possible trades, Kevin now wants to find the lowest price to complete his order of tacos. Given that he can walk back and forth between each of the markets as well as to Torchy's itself, determine the minimum cost to acquire the desired distribution of tacos!

The first line of the input contains $$$t$$$ and $$$e (1 \le t \le 10^4, 0 \le e \le 10^5)$$$, the number of types of tacos and the number of exchanges, respectively.

The next $$$t$$$ lines each contain an integer cost $$$c (1 \le c \le 10^4)$$$ of a each of the different $$$t$$$ types of tacos.

The next $$$e$$$ lines each contain two types of tacos $$$i, j (0 \le i, j < t)$$$ 0-indexed and an integer price $$$p_{i, j} (0 \le p_{i, j} \le 10^4)$$$, representing that Kevin can exchange taco $$$i$$$ for taco $$$j$$$ at the price of $$$p_{i, j}$$$.

Finally, the next $$$t$$$ lines each contain a single value $$$c (1 \le c \le 10^4)$$$, the count desired for the $$$i^{th}$$$ type of taco.

Output a single integer, the amount of money Kevin needs to pay to get his tacos!

3 2
1
3
5
0 1 1
1 2 1
1
2
3

14