1596 . 黑色騎士團的番外野望 Dis-connect
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 1
5 4
1 2 1
2 3 2
3 4 3
4 5 4
5
1 2 3 4 5
1 2 1
2 3 2
3 4 3
4 5 4
5
1 2 3 4 5
Sample Output 1
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 |