410454: GYM104022 L Sheep Village

There is an old country but called Sheep Village which contains $$$n$$$ cities numbered from $$$1$$$ to $$$n$$$ and $$$m$$$ bidirectional roads, each of which connects two different cities.

In Sheep Village, cities are connected through roads. That is, you can always find a path from a city to any other city through some roads. Besides, each road here belongs to at most one simple circuit, where a simple circuit is a set of roads that forms a cyclic path $$$u_1 \to u_2 \to \ldots \to u_m \to u_1$$$ $$$(m \geq 1)$$$ without passing a city more than once. Note that the cyclic paths $$$a \to b \to c \to a$$$, $$$b \to c \to a \to b$$$ and $$$a \to c \to b \to a$$$ correspond to the same circuit.

There are $$$k$$$ sheep living in Sheep Village and also $$$k$$$ lurking wolves. Once all sheep fall asleep, the lurking wolves, led by the wolf king, will launch a blitzkrieg for their static prey. Quietly running through a road does cost energy. For the sake of energy-saving, the wolf king hopes for the best assignments for each wolf to catch a distinct sheep such that the total energy consumed in catching sheep is as small as possible.

As a brilliant strategist as well as a wolf, it's time for you to make the decision to meet the king's requirement.

The first line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ $$$(2 \leq n \leq 10^5, n - 1 \leq m \leq 2 n - 2, 1 \leq k \leq 10^5)$$$, indicating the number of cities in Sheep Village, the number of roads between cities, and the total number of sheep (or wolves) respectively.

The second line contains $$$k$$$ integers, of which the $$$i$$$-th number $$$a_i$$$ $$$(1 \leq a_i \leq n)$$$ indicates the $$$i$$$-th wolf is lurking in the city numbered $$$a_i$$$.

The third line contains $$$k$$$ integers, of which the $$$i$$$-th number $$$b_i$$$ $$$(1 \leq b_i \leq n)$$$ indicates the $$$i$$$-th sheep is sleeping in the city numbered $$$b_i$$$. Some sheep and wolves may live in a city together.

In the next $$$m$$$ lines, each line contains three integers $$$u$$$, $$$v$$$ and $$$w$$$ $$$(1 \leq u, v \leq n, u \neq v, 1 \leq w \leq 10^5)$$$ representing a bidirectional road connecting the cities numbered $$$u$$$ and $$$v$$$ that costs $$$w$$$ energy for an individual wolf running through it quietly. There may exist more than one road between any two cities.

Output an integer in a line representing the minimum total energy consumed.

5 8 4
2 2 3 3
4 4 5 5
1 2 1
2 1 1
1 3 1
3 1 1
1 4 1
4 1 1
1 5 1
5 1 1

8