Byteland có \(n\) thành phố, trong đó có \(k\) thành phố quan trọng mà nhà vua thường xuyên ghé thăm.

Đất nước còn có \(m\) con đường, mỗi con đường nối hai thành phố. Đáng tiếc là tình trạng đường sá quá tệ, khiến nhà vua không thể lái chiếc xe thể thao của mình trên những con đường đó với tốc độ tối đa.

Chi phí sửa chữa từng con đường đã được biết trước. Nhiệm vụ của bạn là chọn những con đường cần sửa chữa sao cho tất cả \(k\) thành phố quan trọng được kết nối với nhau bằng các con đường đã sửa chữa, đồng thời tổng chi phí nhỏ nhất có thể.

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên \(n\), \(k\) và \(m\): số thành phố, số thành phố quan trọng và số con đường. Các thành phố được đánh số \(1,2,\ldots,n\).

Dòng thứ hai chứa \(k\) số nguyên: số hiệu các thành phố quan trọng.

Cuối cùng là \(m\) dòng mô tả các con đường. Mỗi dòng chứa ba số nguyên \(a\), \(b\) và \(c\), cho biết có một con đường hai chiều nối thành phố \(a\) với thành phố \(b\), và chi phí sửa chữa con đường đó là \(c\).

Dữ liệu bảo đảm tồn tại đường đi giữa hai thành phố bất kỳ.

Dữ liệu ra

In ra tổng chi phí nhỏ nhất để sửa chữa các con đường sao cho nhà vua có thể di chuyển giữa tất cả các thành phố quan trọng bằng chiếc xe thể thao của mình.

Ràng buộc

Trong mọi phân nhóm, \(1 \le c \le 10^9\) và \(n \ge k\).

Phân nhóm

1. Nhóm 1 (22 điểm): \(2 \le k \le 5\); \(n \le 20\); \(1 \le m \le 40\).
2. Nhóm 2 (14 điểm): \(2 \le k \le 3\); \(n \le 10^5\); \(1 \le m \le 2 \cdot 10^5\).
3. Nhóm 3 (15 điểm): \(2 \le k \le 4\); \(n \le 1000\); \(1 \le m \le 2000\).
4. Nhóm 4 (23 điểm): \(k=4\); \(n \le 10^5\); \(1 \le m \le 2 \cdot 10^5\).
5. Nhóm 5 (26 điểm): \(k=5\); \(n \le 10^5\); \(1 \le m \le 2 \cdot 10^5\).

Ví dụ

4 3 6
1 3 4
1 2 4
1 3 9
1 4 6
2 3 2
2 4 5
3 4 8

11

Nguồn

Baltic Olympiad in Informatics 2016, ngày thi thứ hai, bài A.