Thành phố nơi Tuấn Anh ở vừa trải qua một trận bão tuyết, băng giá kỷ lục. Hệ thống giao thông của thành phố hoàn toàn bị tê liệt. Theo các thông tin mà chính quyền thu thập được, thành phố có ~n~ nút giao thông (được đánh số từ 1 đến ~n~) và ~m~ tuyến đường hai chiều nối giữa các nút giao thông, chi phí để dọn tuyết trên tuyến đường nối nút giao thông ~i~ với nút giao thông ~j~ là ~c_{i,j}~. Với nguồn ngân sách hiện có của thành phố, thành phố lập dự án lựa chọn một số tuyến đường với tổng chi phí là ít nhất để dọn tuyết nhằm mục đích lưu thông được ~k~ nút giao thông ~i_1, i_2, ..., i_k~ được đánh giá là quan trọng, nghĩa là sau khi dọn tuyết trên các tuyến đường được lựa chọn này có thể di chuyển từ bất kỳ nút giao thông ~i_u~ đến nút giao thông ~i_v~ (~1 \le u < v \le k~).

Tuấn Anh đã đề xuất giúp đỡ thành phố bằng cách thực hiện một dự án lựa chọn một số tuyến đường với tổng chi phí là ít nhất để dọn tuyết nhằm mục đích lưu thông được ~n - k~ nút giao thông còn lại (các nút giao thông khác với ~i_1, i_2, ..., i_k~), dự án này độc lập, thực hiện không phụ thuộc vào dự án của thành phố. Rất nhanh chóng, Tuấn Anh đã lập trình tính được kinh phí cho dự án của thành phố và dự án của mình đề xuất, bạn hãy lập trình giúp Tuấn Anh kiểm tra lại.

Input

• Dòng đầu tiên ghi bốn số nguyên ~n, k, m, t~, trong đó ~n~ (~n \le 100~) là số nút giao thông, ~m~ là số tuyến đường nối giữa các nút giao thông, ~k~ là số nút giao thông mà thành phố đánh giá là quan trọng, ~t~ là loại dự án (~t = 1~ là dự án của thành phố, ~t = 2~ là dự án do Tuấn Anh đề xuất);
• Dòng tiếp theo ghi ~k~ số nguyên dương ~i_1, i_2, ..., i_k~ (các số đôi một khác nhau);
• ~m~ dòng sau, mỗi dòng chứa ba số nguyên ~i, j, c_{ij}~ (~c_{ij} \le 10^6~).

Output

• Một số nguyên là kinh phí của dự án cần tính.

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

Subtasks

• Có 20% số test ứng với 20% số điểm của bài có ~t = 1; k = n~;
• Có 20% số test ứng với 20% số điểm của bài có ~t = 1; k = 2~;
• Có 20% số test khác ứng với 20% số điểm của bài có ~t = 1; k = 3~;
• Có 20% số test khác ứng với 20% số điểm của bài có ~t = 1; k \le 10~;
• Có 20% số test khác ứng với 20% số điểm còn lại của bài có ~t = 2; k \le 10~.