Đề bài

RIFTGATES – Cổng dịch chuyển

Hoành là một người chơi Grim Dawn lâu năm. Cậu bị trò chơi cuốn hút bởi thể loại ARPG với những lối build nhân vật đa dạng và những trận Boss Fight đầy kịch tính. Đặc biệt hơn, Grim Dawn có những cổng dịch chuyển trên bản đồ yêu cầu người chơi kích hoạt để dịch chuyển giữa các cổng khác.

Một hôm, Hoành chợt nghĩ ra bài toán sau:

Bản đồ thế giới Grim Dawn có \(n\) địa điểm và \(m\) con đường có độ dài bất kỳ nối các địa danh với nhau. Trong đó, có \(k\) địa điểm có cổng dịch chuyển. Khi người chơi di chuyển đến một thành phố có cổng dịch chuyển, cổng ở đó được kích hoạt. Sau khi kích hoạt, người chơi có thể dịch chuyển tức thời giữa những cổng đã được kích hoạt trước đó.

Yêu cầu: Xuất phát từ địa điểm số 1 và chưa có cổng nào được kích hoạt, tính quãng đường di chuyển tối thiểu để kích hoạt tất cả các cổng dịch chuyển.

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên dương \(n, m, k\) \((1 \leq k \leq n \leq 10^5; n - 1 \leq m \leq 2 \times 10^5)\).
• \(m\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u, v, w\) \((1 \leq u, v \leq n; 1 \leq w \leq 10^9)\) biểu thị con đường nối địa điểm \(u\) và \(v\) có độ dài \(w\). Dữ liệu đảm bảo luôn có đường đi giữa mọi địa điểm. Giữa hai địa điểm không có hơn một con đường nối trực tiếp.
• Dòng cuối cùng chứa \(k\) số nguyên \(C_i\) — danh sách địa điểm có cổng dịch chuyển. Mỗi địa điểm có nhiều nhất một cổng.

Dữ liệu ra

• Một dòng duy nhất là tổng quãng đường ngắn nhất cần di chuyển để kích hoạt tất cả các cổng dịch chuyển.

Giới hạn

Sample Input 1

3 3 3
1 2 1
1 3 1
2 3 1
1 2 3

Sample Output 1

2

Sample Input 2

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

Sample Output 2

16

Giải thích

• Test 2:
• Người chơi đi từ địa điểm 1 → 2 (\(+1\)).
• Kích hoạt cổng dịch chuyển tại địa điểm 2.
• Đi từ địa điểm 2 → 3 (\(+5\)), kích hoạt cổng dịch chuyển tại địa điểm 3.
• Dịch chuyển tức thời về địa điểm 2.
• Đi từ địa điểm 2 → 4 (\(+10\)), kích hoạt cổng dịch chuyển tại địa điểm 4.
• Tổng quãng đường = 1 + 5 + 10 = 16.
  ```