Thành phố vừa hứng chịu một siêu bão khiến toàn bộ mạng lưới cáp quang viễn thông bị đứt dẫn. Theo khảo sát từ sở thông tin, mạng lưới thành phố gồm ~n~ trạm thu phát sóng (được đánh số từ ~1~ đến ~n~) và ~m~ tuyến cáp quang hai chiều nối giữa các trạm. Chi phí để sửa chữa tuyến cáp nối giữa trạm ~u~ và trạm ~v~ là ~w_i~.

Chính quyền thành phố hiện có hai phương án ưu tiên sửa chữa độc lập, cả hai đều nhắm đến mục tiêu tối ưu hóa (giảm thiểu) tổng chi phí:

• Dự án của thành phố (Loại ~1~): Sửa chữa một số tuyến cáp sao cho ~k~ trạm trọng điểm ~i_1, i_2, \dots, i_k~ (như bệnh viện, ủy ban, đài phát thanh) có thể liên lạc được với nhau, tức là có đường đi giữa bất kỳ trạm ~i_u~ và ~i_v~ nào thuộc nhóm này.

• Dự án mở rộng (Loại ~2~): Sửa chữa một số tuyến cáp sao cho ~n - k~ trạm dân sự còn lại (các trạm không nằm trong danh sách trạm trọng điểm ở trên) có thể liên lạc được với nhau.

Là kỹ sư trưởng của dự án, bạn được giao nhiệm vụ viết chương trình tính toán tổng chi phí tối thiểu để hoàn thành một trong hai loại dự án trên.

Input

• Dòng đầu ghi ~4~ số ~n, k, m, t~, trong đó ~n~ ~(n \le 100)~ là tổng số trạm thu phát sóng, ~m~ ~(m \le 1000)~ là số tuyến cáp quang, ~k~ là số lượng trạm trọng điểm, ~t~ là loại dự án (~t = 1~ là dự án thành phố, ~t = 2~ là dự án mở rộng).

• Dòng tiếp theo ghi ~k~ số nguyên dương ~i_1, i_2, \dots, i_k~. Các số đôi một khác nhau.

• ~m~ dòng tiếp, mỗi dòng chứa ba số nguyên ~u, v, w_i~ thể hiện có tuyến cáp nối giữa trạm ~u~ và trạm ~v~ với chi phí sửa chữa là ~w_i~ ~(w_i \le 10^6)~.

Dữ liệu đảm bảo luôn có đáp án.

Output

Một số nguyên duy nhất là tổng chi phí tối thiểu để thực hiện dự án được yêu cầu.

Scoring

Sample Input 1

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

Sample Output 1

2

Sample Input 2

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

Sample Output 2

4