410609: GYM104065 E Hammer to Fall

Boboland is a beautiful country with $$$n$$$ cities and $$$m$$$ two-way roads, ruled by King Bobo. A two-way road $$$(u,v,w)$$$ connects city $$$u$$$ and city $$$v$$$ with distance $$$w$$$. It is guaranteed that for each city in Boboland, at least one road connects to it.

There were $$$a_i$$$ residents in the $$$i$$$-th city, living a happy and peaceful life until the day came when it began to fall hammers! Specifically, every day hammers will start to fall on exactly one city of Boboland, causing all residents in that city to die.

As the king of Boboland, Bobo needs to deal with this situation. But unfortunately, he doesn't know why this disaster would happen, and he can't figure out a way so that the hammer would eventually stop falling. Despite this, he figured out the following "dynamic zero-casualty policy": it is OK as long as when the hammer falls on some city someday, all residents in that city have already been transferred to some other city so that no death is incurred.

After talking with the prophet in Boboland, Bobo has gained the following information: in the upcoming $$$q$$$ days, hammers will fall on cities $$$b_1,b_2,...,b_q$$$ in order. At any time, Bobo can arrange to transfer any single resident at some city $$$u$$$ to some adjacent city $$$v$$$ with cost $$$w$$$ if a road $$$(u,v,w)$$$ exists. Multiple residents can be transferred simultaneously. Also, any resident can be transferred multiple times.

Bobo wants to ensure no resident dies after the $$$q$$$ days, using as little cost as possible. But, as always, a king never does the counting by himself, so you have to calculate the minimum cost to achieve the goal.

Since the answer might be large, you should output the answer modulo $$$998\,244\,353$$$. Note that your minimization target is still the cost before modulo, not after.

The first line contains three integers $$$n,m,q$$$ $$$(2 \leq n \leq 10^5, 1\leq m,q\leq 10^5)$$$, denoting the number of cities in Boboland, the number of roads in Boboland, and the length of information from the prophet, respectively.

The second line contains $$$n$$$ integers $$$a_1,a_2,...,a_n$$$ $$$(1\leq a_i\leq 10^9)$$$, denoting the number of residents in each city.

The $$$m$$$ lines follow, each line containing $$$3$$$ integers $$$u,v,w$$$ $$$(1\leq u,v\leq n,u\neq v,1\leq w\leq 10^9)$$$, denoting a two-way road $$$(u,v,w)$$$ in Boboland. It is guaranteed that for each city in Boboland, at least one road connects to it.

The next line contains $$$q$$$ integers $$$b_1,b_2,...,b_q$$$ $$$(1\leq b_i\leq n)$$$, denoting the city on which the hammer will fall in the upcoming $$$q$$$ days, in order.

Output an integer in one line, denoting the minimum cost to achieve Bobo's goal, modulo $$$998\,244\,353$$$.

3 2 2
1 1 1
2 3 10
1 2 1
3 2

12

2 1 10
5000 5000
1 2 10000
1 2 2 1 2 2 1 1 1 2

550000000

For the first sample test, an optimal arrangement is to transfer the only resident at city $$$3$$$ to city $$$2$$$ at the beginning of the second day and then transfer the two residents at city $$$2$$$ to city $$$1$$$ at the beginning of the third day. The total cost is $$$10\cdot 1+1\cdot 2=12$$$.