TopCoder

Thumb 20160216205031 xujvl.thumb.700 0
自動姬
壓不贏 $fhvirus$

User's AC Ratio

100.0% (9/9)

Submission's AC Ratio

51.9% (27/52)

Tags

Description


黑色騎士團終於決定了攻打大不列顛帝國的戰略。

在大不列顛帝國的國土當中,有著許多的城市,城市與城市之間會有道路相互連通。

在這些城市當中,有些特別的城市兼具有軍事堡壘的功能。

想要完全的佔領大不列顛帝國,必須要摧毀一些道路,讓軍事堡壘城市之間兩兩無法到達。

對於兩個城市,如果他們之間直接有道路連通,或著他們都同樣可以到達另一個城市,那我們說他們是可到達的。

摧毀道路是需要花錢的。經過了許久的研究,黑色騎士團發現對於每一條道路而言,摧毀它必然會造成某些城市之間不可到達。

請問如果要佔領大不列顛帝國,最少要花多少錢摧毀道路?

Input Format


輸入檔的第一行會有兩個整數 n m,分別代表大不列顛帝國中城市的數量即道路的數量。

接下來有 m 行,每行有三個正整數 i j c,代表城市 i 跟城市 j 之間有道路連通,而摧
毀這條道路需要 c 的金錢。

然後會有一個整數 k ,軍事堡壘城市的數量。

接下來有 k 個整數,每一個分別代表一個軍事堡壘城市的編號。

1 ≦ n ≦ 100,000

0 ≦ k ≦ n

1 ≦ i, j ≦ n

1 ≦ c ≦ 20,000

城市的編號從 1~n

Output Format


請輸出一個貌似答案的整數。

Sample Input

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

Sample Output

10

Hints

Problem Source

原TIOJ1596 / Problem Setter: suhorng

Subtasks

No. Testdata Range Score
1 0 5
2 1 5
3 2 5
4 3 5
5 4 5
6 5 5
7 6 5
8 7 5
9 8 5
10 9 5
11 10 5
12 11 5
13 12 5
14 13 5
15 14 5
16 15 5
17 16 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 3000 65536 262144 1
1 3000 65536 262144 2
2 3000 65536 262144 3
3 3000 65536 262144 4
4 3000 65536 262144 5
5 3000 65536 262144 6
6 3000 65536 262144 7
7 3000 65536 262144 8
8 3000 65536 262144 9
9 3000 65536 262144 10
10 3000 65536 262144 11
11 3000 65536 262144 12
12 3000 65536 262144 13
13 3000 65536 262144 14
14 3000 65536 262144 15
15 3000 65536 262144 16
16 3000 65536 262144 17