This page is still under construction.

Parts of this page are still being built. What you see may change.

Not enough electricity

Time limit1sMemory limit256 MB

Summary
Connect every city to exactly one of the given power plants with minimum total cable cost.
Level

Medium5 of 10

Topics
Minimum spanning tree, Union-find
Solved
No attempts yet

Problem

Seogang leads in both software and hardware, so people call it an IT powerhouse. It has been ranked the best country to live in since 2015, and the number of foreign visitors has grown a lot since then. Electricity consumption grew with them, and the whole country is now short of power.

The president decided to start the YNY power plant project, whose development just finished. The plant buildings already stand in certain cities, so the only extra cost is the cost of laying cables between cities. Cables are expensive, so the total cost has to be as small as possible while every city receives electricity.

There are NN cities, MM cables that can be installed, and KK cities that hold a plant. A city drawing electricity from two plants at once wastes power, so every group of cities joined by cables must contain exactly one plant. A city that holds a plant powers itself even when no cable reaches it.

Choose the cables to install and report the minimum total cost of supplying every city.

Input

The first line contains the number of cities NN (1≤N≤10001 \le N \le 1000), the number of cables that can be installed MM (1≤M≤1000001 \le M \le 100000), and the number of power plants KK (1≤K≤N1 \le K \le N).

The second line contains the numbers of the KK cities that hold a plant. The numbers are distinct.

Each of the next MM lines contains one cable as uu, vv, ww. Installing the cable between city uu and city vv costs ww. ww is a positive integer no greater than 1000010000.

A way to supply every city always exists.

Output

Print on one line the minimum cost of installing cables so that every city receives electricity.

Examples3

  1. Example 1

    Input
    9 14 3
    1 2 9
    1 3 3
    1 4 8
    2 4 10
    3 4 11
    3 5 6
    4 5 4
    4 6 10
    5 6 5
    5 7 4
    6 7 7
    6 8 4
    7 8 5
    7 9 2
    8 9 5
    
    Expected output
    22
  2. Example 2

    Input
    4 5 1
    1
    1 2 5
    1 3 5
    1 4 5
    2 3 10
    3 4 10
    
    Expected output
    15
  3. Example 3

    Input
    10 9 5
    1 4 6 9 10
    1 2 3
    2 3 8
    3 4 5
    4 5 1
    5 6 2
    6 7 6
    7 8 3
    8 9 4
    9 10 1
    
    Expected output
    16