Có N thành phố ở Byte và có k thành phố trong số chúng là các thành phố quan trọng (k<=n).

Có M con đường hai chiều ở Byte, mỗi con đường nối giữa hai thành phố. Một số con đường đã xuống cấp, cần phải được sửa chữa lại. Với mỗi con đường, chi phí sửa chữa được biết trước. 

Nhiệm vụ của bạn là hãy chọn những con đường cần sửa chữa sao cho k thành phố quan trọng sẽ được nối với những con đường được sửa chữa và tổng chi phí sửa chữa là ít nhất

Dữ liệu vào : CITIESK.INP

• Dòng đầu tiên gồm 3 số n, k, m: Số thành phố, số thành phố quan trọng và số con đường. Các thành phố được đánh số từ 1,2,3,…,n
• Dòng thứ 2 là k số: số thứ tự các thành phố quan trọng
• Cuối cùng là mô tả n con đường, mỗi dòng gồm 3 số: a, b, c trong đó thành phố a sẽ nối với thành phố b và chi phí sửa chữa là c

Dữ liệu ra: CITIESK.OUT

Tổng chi phí nhỏ nhất để sửa chữa các con đường kết nối tất cả các thành phố quan trọng của đất nước

Giới hạn: 1 ≤ c ≤ 10⁹ và n ≥ k.

Subtask 1 (22 test): 2 ≤ k ≤ 5;  n ≤ 20; 1 ≤ m ≤ 40

Subtask 2 (14 test): 2 ≤ k ≤ 3; n ≤ 10^5; 1 ≤ m ≤ 2 ×10⁵

Subtask 3 (15 test): 2 ≤ k ≤ 4; n ≤ 1000; 1 ≤ m ≤ 2000

Subtask 4 (23 test): k = 4;  n ≤ 10⁵; 1 ≤ m ≤ 2 ⋅ 10⁵

Subtask 5 (26 test): k <= 7; n ≤ 10⁵ ; 1 ≤ m ≤ 2 ⋅ 10⁵

^{Base on THREE, QBBUILD, NKBUILD}