Xe khách là \(1\) phương tiện hữu dụng và đỡ tốn kém để di chuyển từ địa điểm này đến địa điểm khác nên rất được mọi người sử dụng. Do đó, Phó Sắc Cường - \(1\) doanh nhân nổi tiếng - cũng muốn mở \(1\) công ty xe khách tại thành phố Hà Nội. Việc đầu tiên mà Cường phải đối mặt là phải viết chương trình giải quyết bài toán sau:

Bản đồ thành phố Hà Nội có thể được biểu diễn dưới dạng đồ thị vô hướng gồm \(N\) đỉnh và \(M\) cạnh, cạnh thứ \(i\) nối giữa \(2\) địa điểm \(u_i\) và \(v_i\) với thời gian để đi hết con đường này là \(w_i\) phút. Giữa \(2\) địa điểm bất kỳ luôn tồn tại đường đi trực tiếp hoặc gián tiếp.

Cường quyết định đặt công ty ở địa điểm \(1\), trùng với bến xe Mỹ Đình, là địa điểm rất nhiều người hay đến. Đồng thời, Cường chỉ tiếp nhận những vị khách có yêu cầu đi từ địa điểm \(s\) (\(2 \le s \le N\)) đến địa điểm \(1\).

Với mỗi chuyến xe sẽ phục vụ đúng \(K\) khách. Giả sử khách \(i\) xuất phát ở địa điểm \(s_i\) và muốn đến địa điểm \(1\). Tìm \(1\) hành trình cho xe khách xuất phát từ địa điểm \(1\), và đưa được tất cả \(K\) người cùng đến địa điểm \(1\). Hành trình được gọi là tối ưu nếu thời gian vị khách đến được địa điểm \(1\) muộn nhất là sớm nhất có thể.

Lưu ý: Thời gian để \(1\) người lên xe hoặc xuống xe là không đáng kể (coi như bằng \(0\)).

Input

• Dòng \(1\): Gồm \(3\) số \(N\), \(M\), \(K\). (\(1 \le N,M \le 10^5\); \(1 \le K \le 15\))
• Dòng \(2\): Gồm \(K\) số nguyên \(s\) biểu thị cho địa điểm xuất phát của \(k\) vị khách. (\(2 \le s \le N\))
• \(M\) dòng tiếp theo, mỗi dòng gồm \(3\) số \(u\), \(v\) và \(w\) biểu thị cho \(1\) cạnh của đồ thị. (\(1 \le u,v \le N\); \(u \ne v\); \(1 \le w \le 10^9\))

Output

• \(1\) số duy nhất là thời gian vị khách cuối cùng đến được địa điểm \(1\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(K = 1\).
• Subtask \(2\) (\(30\%\) số điểm): \(K \le 5\).
• Subtask \(3\) (\(20\%\) số điểm): \(N \le 2000\); \(1 \le M \le 5000\).
• Subtask \(4\) (\(30\%\) số điểm): Không có điều kiện gì thêm.

Example

6 8 2
2 5
1 2 4
2 4 2
4 3 3
3 1 4
4 1 5
3 5 5
5 3 1
5 6 7

15